Going beyond persistent homology using persistent homology
Authors: Johanna Emilia Immonen
Amauri H Souza
Vikas Garg
Venue: NeurIPS 2023 oral (2023)
Keywords: graph representation learning
topological deep learning
persistent homology
graph neural networks

Abstract: Representational limits of message-passing graph neural networks (MP-GNNs), e.g., in terms of the Weisfeiler-Leman (WL) test for isomorphism, are well understood. Augmenting these graph models with topological features via persistent homology (PH) has gained prominence, but identifying the class of attributed graphs that PH can recognize remains open.  We introduce a novel concept of color-separating sets to provide a complete resolution to this important problem. Specifically, we establish the necessary and sufficient conditions for distinguishing graphs based on the persistence of their connected components, obtained from filter functions on vertex and edge colors. Our constructions expose the limits of vertex- and edge-level PH, proving that neither category subsumes the other. Leveraging these theoretical insights, we propose RePHINE for learning topological features on graphs. RePHINE efficiently combines vertex- and edge-level PH, achieving a scheme that is provably more powerful than both. Integrating RePHINE into MP-GNNs boosts their expressive power, resulting in gains over standard PH on several benchmarks for graph classification.

Going beyond persistent homology using persistent homology
Johanna Immonen' University of Helsinki
Amauri H. Souza' Aalto University Federal Institute of Ceará amauri www.aaaauaaaaaaaooooooo fi
Vikas Garg Aalto University
johanna. x. immonen@helsinkii.cc
Yai Ltd vgarg&csail mit. edu
Abstract
Representational limits of message-passee paasging graph neural networks (MP-GNNs), e.g., in terms of the Weisfeiler-Leman (WL) test for isomorphism, are well under- stood. Augmenting these graph models with topological features via persistent homology (PH) has gained prominence, but identifying the class of attributed graphs that PH can recognize remains open. We introduce novel concept of color-separating sets to provide a complete resolution to this important problem. Specifically, we establish the necessary and sufficient conditions for distinguishing graphs based on the persistence of their connected components, obtained from filter functions on vertex and edge colors. Our constructions expose the limits of vertex- and edge-level PH, proving that neither category subsumes the other. Leveraging these theoretical insights, we propose RePHINE for learning topological features graphs. RePHINE efficiently combines vertex- and edge-level PH, achieving a scheme that is provably more powerful than both. Integrating RePHINE into MP-GNNs boosts their expressive power, resulting in gains over standard PH on several benchmarks for graph classification.
1 Introduction
Topological data analysis (TDA) is rapidly growing field that provides tools from algebraic topology for uncovering the shape (or structure) of data, allowing for efficient feature extraction. Its flagship tool is persistent homology (PH) [8], which seeks to characterize topological invariants (c.g.. con- nected components, loops) of an underlying manifold based on data samples. Notably, PH has been successfully applied in many scientific domains, including computer vision [17, 27], drug design [23], fluid dynamics [24], and material science [25].
For graphs, PH has been used to provide global topological signatures for graph-level prediction tasks [2, 12, 14, 33, 39] and act as local message modulators in graph neural networks (GNNs) for node- level tasks [4, 40]. By leveraging learnable filtration/vecttrizatii
predicctioon
maps, PH has also been integrated into neural networks as a building block in the end-to-end learning process [2, 3, 13, 15, 26). These strategies allow to exploit topological features to boost the predictive capabilities of graph models. However, in stark contrast with the developments on the representational power of GNNs [1, 11. 28- 30, 34, 35, 37], the theoretical properties of PH graphs remain much less explored. For instance, open questions include: Which graph properties can PH capture? What is the characterization of pairs of graphs that PH cannot separate? Can improve the expressivity of PH graphs?
In recent work, Rieck [32] discusses the expressivity of PH on graphs in terms of the Weisfeiler- Leman (WL) hierarchy [36]. The paper shows that, given different &L colorings, there exists filtration such that the corresponding persistence diagrams differ. This result provides a lower bound for the expressivity in terms of WI. hierarchy, but it does not describe the class of graphs which can be distinguished via PH. In this paper, we aim to fully characterize this class of graphs.
Equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Theoretical contributions of this work
On vertex-level filtrations (Section 2 and Section 3.1): Inconsistency issues due to injective vertex filtrations Real holes (d oo) = Component-wise colors Almost holes (b # * oo) Separating sets Distinct almost holes = Color-separating set Birth time of persistence tuples = Vertex color The expressive power of vertex-color filtrations
Lemma
Lemma 2
Lemma 3
Lemma
Lemma 5
Theorem
On edge-level filtrations (Section 3.2): Almost holes Disconnecting sets Reconstruction of disconnecting sets
Lemma
Lemma 7
The expressive power of edge-color filtrations
Theorem 2
Vertex-level vs. edge-level filtrations (Section 3.3):
Vertex-level persistence yf edge-level persistence, and vice-versa
Theorem 3
New method (RePHINE) (Section 4): RePHINE is isomorphism invariant
Theorem 4 Theorem 5
RePHINE vertex-, edge- and vertex- edge-level diagrams
Figure 1: Overview of our theoretical results.
We study the expressive power of PH on attributed (or colored) graphs, viewed as 1-dim simplicial complexes. We focus the class of graph filtrations induced by functions these colors. Impor- tantly, such a class is rather general and reflects choices popular methods (e.g.. topological GNNs [15]). We first analyze the persistence of connected components obtained from vertex colors. Then, we extend our analysis to graphs with edge colors. To obtain upper bounds on the expressive power of color-based PH, we leverage the notion of apparatingddscooneetiin
sets. This allows to establish the necessary and sufficient conditions for the distinguishability of two graphs from O-dim persistence diagrams (topological descriptors). We also provide constructions that highlight the limits of vertex- and edge-color PH, proving that neither category subsumes the other.
Based on our insights, we present RePHINE (short for "Refining PH by Incorporating Node-color into Edge-based filtration"), simple method that exploits subtle interplay between vertex- and edge-level persistence information to improve the expressivity of color-based PH. Importantly, RePHINE can be easily integrated into GNN layers and incurs no computational burden to the standard approach. Experiments support our theoretical analysis and show the effectiveness of RePHINE three synthetic and six real datasets. We also show that RePHINE can be flexibly adopted in different architectures and outperforms PersLay [2] popular topological neural net.
In sum, our contributions are three-fold:
(Theory) We establish a series of theoretical results that characterize PH on graphs, including bounds on the expressivity of vertex- and edge-level approaches, the relationship between these approaches, and impossibility results for color-based PH as summarized in Figure 1.
(Methodology) We introduce new topological descriptor (RePHINE) that is provably more expressive than standard O-dim and 1-dim persistence diagrams.
(Experiments) We show that the improved expressivity of our approach also translates into gains in real-world graph classification problems.
2 Preliminaries
We consider arbitrary graphs G =VV, (V,E,c, X) with vertices V = 7(11 (1,2,...,. edges E C
V x V and vertex-coloring function e: V - X, where X denotes a set of m colors or features
{Z), .2...., } such that each color 2; E Rd We say two graphs G (V, E, c, and G"

---

VV',',c'X'' are isomorphic (denoted by G = G") if there is a bijection g. V + V' such that (v,w) w) E Eff (g(v), g(w)) E' and c = c' e g. Here, we also analyze settings where graphs have
an edge-coloring function 1.
A filtration of a graph G is finite nested sequence of subgraphs of G. that is, G1 C G2 -.. G. Although the design of filtrations can be flexible [12], a typical choice consists of leveraging a of [()())). Then, a filtration induced by f is an indexed set ((())) } such that G ((((0)) S G is the subgraph induced by the set of vertices Vi((()) {u E V [(v) S (()())). Note that filtration functions which give the same permutation of vertices induce the same filtration. Persistent homology keeps track of the topological features of each subgraph in filtration. For graphs G, these features are either the number of connected components or independent cycles (i.c., 0- and I-dim topological features, denoted respectively by the Betti numbers &y and ( and can be efficiently computed using computational homology. In particular, if' a topological feature first appears in G (((()) and disappears in G (m(())) then we encode its persistence as a pair
vertex filter (or filtration) function f V + IR for which we can obtain a permutation n vertices such that [()(11) & f(( ................
if a feature does not disappear in G (m(()) = G. then its persistence is (f (T((). 2.). The collection of all pairs forms a multiset that we call persistence diagram [5]. We use 2 and D to refer to the persistence diagrams for O- and I-dim topological features respectively. Appendix A provides a more detailed treatment for persistent homology.
Recent works have highlighted the importance of adopting injective vertex filter functions. Hofer et al. [13] show that injectivity of parameterized functions fo V - I is a condition for obtaining well-defined gradients with respect to the parameters 0, enabling end-to-end filtration learning. Also, Horn et al. [15] show that for any non-injective function, we can find an arbitrarily close injective one that is at least as powerful at distinguishing non-isomorphic graphs as the original (non-injective) function. However, Lemma 1 shows that filtrations induced by injective functions on vertices may result in inconsistent persistence diagrams; namely, different diagrams for isomorphic graphs.
Lemma 1 (Injective vertex-based filtrations can generate inconsistent persistence diagrams). Consider persistence diagrams obtained from injective vertex filter functions. There are isomorphic graphs G = G' such that their persistence diagrams are different, i.e., DG + De-
To avoid inconsistent diagrams, we need to employ permutation equivariant filter functions - see [32, Lemma 2]. Common choices include vertex degree [12], eigenvalues of the graph Laplacian [2], and GNN layers [13], which are permutation equivariant by construction. Another option is to define graph filtrations based on vertex/edge colors [15], which are also equivariant by design, i.e., if G = G' with associated bijection g. then c(v) c'(g(v) Vo E V. Notably, volor-based filtrations generalize the GNN-layers case since we could redefine vertex/edgec-colring functions to take the graph structure as an additional input. Thus, we now turn our attention to color-based filtrations.
Cased filtrations. Let f X + R be an injective function. Therefore, f must assign strict total order for colors, i.e., there is permutation π. : (l..... m} + {1.... m) such that f(*x1)) < < (f)(m)). ). We define the vertex-color filtration induced by f as the indexed set pm ) where G, (V,, Fa, Gr Xi). with X; {> (2)...... Fx()))) ). V2 {u E V c(v) e X,). and G, {(e, c(r))
E Vi}. Similarly, can define the edge-color filtration filtvaaioon induced by f as [m where G. = (V, E,, X2) with X, = {za()).... E., (())) }. E, {(v, w) E E I(0, E X,). and 1, = [((e, [(, [v,,w( (v.w) E.).
X,), E. ( w) E E c(v) X,, c())(
pm
We denote the elements of a persistence diagram D as pairs (f(z!)), f(x(4)) where (()) X are the colors associated with the birth and death of a hole (topological feature) in a filtration induced by f(-). In the following, we use the notation {f J to denote multisets.
3 The power of O-dim persistent homology under color-based filtrations
In this section, we analyze the representational power of persistent homology when adopting color- based filtrations. We focus on the persistence of connected components (0-dimensional holes). We separately discuss vertex-color (Section 3. and edge-color (Section 3.2) filtrations, and then compare these approaches in Section 3.3. Proofs for all Lemmas and Theorems are in Appendix B.
3.1 Vertex-color filtrations
To help characterize the expressivity of persistent homology, we propose classifying persistence pairs (f(x((),, f(((0)) as either real holes, almost holes, trivial holes. In particular, if fz)(4) # co
3

---

) we say the pair (f(x!"), f(x(4)) is an almost hole. If fx((0) = f(x((1)) the pair is called a trivial hole. Finally, we call (f(x!()), f()l(d) real hole if f(zld) = CO.
and f(x(()) o f(x(()),
3.1.1 Real holes as connected components
Real holes denote topological features that persist until filtration reaches the entire graph. Thus, real holes from O-dim persistence diagrams are associated with connected components, regardless of the filtration. Regarding the relationship between filtrations and real holes, Lemma 2 establishes the necessary and sufficient condition for the existence of filtration that produces persistence diagrams with distinct real holes. Such a condition associated with the notion of component- -wise colors. Formally, let G and G" be two graphs with connected components Ci...., Cs. and Ci...., Caa,, respectively. Also, let X; = {c(v) o Vc,} } be the set of colors in C₂ and, similarly, X be the colors in Cy. We say that G and G' have distinct component-wise colors if Hf {X; Bi=I & P
Lemma 2 (Equivalence between component-wist colors and real holes). Let G and G' be two graphs. There exists some vertex-color filtration such that their persistence diagrams Do and Do have different multisets of real holes iff G and G' have distinct component-wise colors.
3.1.2 Almost holes as separating sets
Now we turn our attention to the characterization of almost holes. Our next result (Lemma 3) reveals the connection between almost holes and separating sets. Here, separating set S of a graph G is subset of its vertices whose removal disconnects some connected component of G.
Lemma 3 (Almost holes and separating sets). Regarding the relationship between almost holes and separating sets, the following holds:
1. Let (f(x!")), (()(1) be an almost hole from a vertex-color filtration. Then the set S {w E
V f(c(w)) 2 (() is a separating set of G.
}
2. Let S be a separating set of G that splits a connected component C S G into k components
C1, C2.......,, Then, there exists a filtration that produces k 1 almost holes if the set of colors of vertices in _ Vc, is disjoint from those of the remaining vertices, i.e, {c(v)
V V....VV. n (c(u) v E Vc. = 0.
The relationship between almost holes and separating sets elucidated in Lemma raises the question we can use separating sets (obtained from colors) to compare almost holes across different graphs. The answer no: even if the diagrams of two graphs only differ in their multi- sets of almost holes, the graphs might not have separat- ing sets that split them into different numbers of com- ponents. For instance, consider the graphs in Figure 2, where numbers denote filter values. The persistence dia- grams De = (1, x), ( (2, 3), (2, 3), (3, 3), (3, 4), (4,4) (1,, co), 2, 3), (2, 4). (3, (3, (3, (4, only differ in almost holes. Still, we cannot pick colors whose removal of associated vertices would result in differ- ent numbers of components.
and Do
G
G'
Figure 2: We cannot use color-based sepa- rating sets to compare almost holes across graphs. Although these filtrations produce different almost holes, there is way remove colors s.t. the resulting graphs have different numbers of components.
Next, we introduce the notion of selaratip sets (Def- inition 1). Importantly, Lemma leverages this definition to characterize the graphs that be distinguished based on almost holes. Specifically, it establishes that whenever the diagrams of two graphs differ in their multiset of almost holes,
we can build color-separating set.
Definition (Color-separating sets). A color-separating set for a pair of graphs (G, is a ser of colors Q such that the subgraphs induced by V VV E V c(w) E Q) and (' E V [d(((()) E Q} have distinct component-wist colors.
We note that when G and G' have identical component-wise wise colors, the sets {w E V c(w) E Q} and (w E V dl (w) E Q) induced by the color-separating set Q are separating sets for G and G².

---

Lemma 4 (Distinct almost holes imply distinct color-separating sets), Let De. De be persistence diagrams for G and G'. If the diagrams Dg. De differ their multisets of almost holes, then there is a color-separating set for G and G'.
3.1.3 Bounds on the expressivity of vertex-color persistent homology
Regardless of the filtration, vertex-color PH always allows counting the numbers of connected components and vertices of graph. If all vertices have the same color, then we cannot have any expressive power beyond 3 and [V] when all vertices are added simultaneously, there cannot be almost holes as the finite living times of the holes are O. Also, all real holes are identical, and we have 'DD K (1, (1, (1) (1, 1)... (1,1) with |Dd = [V
For graphs with 2 colors, Lemma shows that sets of birth times correspond to vertex colors. As a consequence, if the multisets of vertex colors differ for graphs G and G', then the corresponding persistence diagrams are also different in all filtrations.
Lemma (Equivalence between birth times and vertex colors). There is bijection between the multiset of birth times and the multiset of vertex colors in any vertex-color filtration.
From Lemma we can recover the multiset of colors from the persistence diagram and, consequently, distinguish graphs with different multisets. However, persistent homology uses vertex colors as input, and we not need persistence diagrams to construct or compare such multisets. This highlights the importance of death times to achieve expressivity beyond identifying vertex colors. In fact, for non-trivial cases, the expressivity highly depends on the choice of filtration.
We have discussed the importance of color-separating sets (Lemma 4) and component-wise vertex colors (Lemma 2). With these notions, Theorem formalizes the limits of expressivity that may be achieved with suitable filtration and characterize which pairs of graphs can, at best, be distinguished by comparing their persistence diagrams. Here, we only consider pairs of graphs that cannot be distinguished by their multisets of colors, as this corresponds to a trivial case.
Theorem 1 (The expressive power of vertex-color filtrations). For any two graphs G and G' with identical multisets of colors (c(v) : V = (d( : E V' there exists a filtration such that D2 + De if and only if there is color-separating set for G and G².
3.2 Edge-color filtrations
We now consider the expressivity of O-dim persistent homology obtained from edge-color filtrations. The persistence diagrams are constructed exactly the same way. However, in this case, all holes are born at the same time (all vertices appear in Go). This implies that all real holes are identical. Also, the diagrams do not contain trivial holes since Go does not have edges. All holes are either real holes or almost holes (of the form (0, d)). We also note that persistence diagrams will always have almost holes unless the graph is edgeless.
G
G'
G
G'
(a)
(b)
Figure 3: (a) G and G' differ in their multisets of colors, but no edge-color filtration can distin- guish them. For instance, assume that f('blue") = < 2 f('orange"). Then, Do Dg (0, oo), (0, 1). (0, 1), (0, 1).. The same holds for f('blue") > f('orange"). (b) Graphs that have different disconnecting sets, for which we can find filtrations that lead identical diagrams.
Analogously to separating sets in vertex-color filtrations, Lemma 6 characterizes edge-based almost holes as disconnecting sets - a set of edges whose removal would increase the number of components.
Lemma 6 badge almost holes disconnecting sets). Let (0, f (x((1) be almost hole from an edge-color filiration. Then S {e E s(((e) ((x(d)) is disconnecting set of G.
Lemma 6 tells us how construct a disconnecting set from an almost hole. Now, suppose we are given a disconnecting set S. Can we build edge-color filtration for which S can be obtained from
5

---

an almost hole? In other words, can we obtain diagram with an almost hole (0, (zx())) such that {e E E' f(((e)) 2 f(x(d)}} is equal to S? Lemma 7 shows that if the colors of edges in S are distinct from those E \ S, then there is a filtration that induces persistence diagram with an almost hole from which we can reconstruct S.
Lemma 7 (Reconstructing a disconnecting set). =V, be graph and S C E be disconnecting set for G. If the set of colors of S is disjoint from that of E S, then there exists filtration such that S {E E f(((e)) 2 f(x(d)) } for an almost hole (0, f(xld)) DD
3.2.1 Bounds on the expressivity of edge-color persistent homology
Similar the vertex-color case, in any edge-color filtration, have that [D0] [V| and the number of real holes is 3 Also, the lowest expressivity is achieved when all edges have the same color. In this case, two graphs with different numbers of vertices connected components have different persistence diagrams (and can be distinguished); otherwise, they cannot be distinguished.
We have seen in Lemma 5 that vertex-color filtrations encode colors as birth times. In contrast, birth times from edge-color filtrations always trivially equal to zero. Thus, cannot generalize Lemma 5 to edge-color filtrations. Instead, we can show there are graphs with different multisets of edge colors such that the graphs have the same persistence diagrams for any filtration (see Figure 3())..
Let now consider lower limits for graphs with two graphs have different disconnecting sets (obtained from colors), there are filtrations that induce the same persistence diagrams. To this behavior, consider the two graphs in Fig- ure 3(b), where the deletion of blue edges disconnects one of the graphs but not the other. Al- though can build edge-color filtration that separates these graphs (i.e., Do D if we choose f(( (""green") = 3, = ('orange") = 2, and f("blue") = 1, we obtain D if graphs have different sets
1 edge colors. We can show that even
DE =
{(0, oo), (0, 1), (0, 2), (0, 2). (0, 2). (0, 2) Interestingly, of edge colors, we might still find filtrations that induce identical diagrams. The reason is that unlike vertex-color filtrations where trivial holes make sure that all vertices are represented the diagrams, in edge-color filtrations there are no trivial holes, As result, persistence diagrams from edge-color filtrations do not account for edges that do not lead to the disappearance of connected components.
Lemma 6 and Lemma 7 showed that edge-based almost holes be characterized disconnecting sets, somewhat analogously to vertex-based almost holes as separating sets. We complete the analogy by introducing the notion of color-disconeecting sets in Definition 2. We then use this notion to fully characterize the the expressive power of edge-color persistent homology in Theorem 2. More specifically, the existence of diglo-ddsconnecting set between given pair of graphs is necessary and sufficient condition for distinguishing them based on O-dimensional persistence diagrams.
Definition (Coloe-disconnectnng sets). A color-discomnecting set for a pair of graphs (G, G') is set of colors Q such that if we remove the edges of colors in Q from G and G', obtain subgraphs with different numbers of connected components.
Theorem 2 (The expressive power of edge-color filtrations). Consider two graphs G and G'. There exists edge-color filtration such that D + Do if and only if there is color-disconnecting set for G and G'.
3.3
Vertex-color versus edge-color filtrations
To compare vertex- and edge-color persistence diagrams, we consider graphs with vertex-coloring functions c(-) from which we derive edge-coloring ones 1(.). In particular, for a graph G' (V, E, c, X), its edge-coloring function 1 > X2 is defined I(0, w) = (c(v), c(w)).
G'
(c)
Figure 4: Illustration of graphs that cannot be distinguished based on (a) edge-color filtrations, (b)
vertex-color filtrations, and (c) both vertex- and edge-color filtrations.

---

Recall that only vertex-color filtrations can 1) encode multisets of colors and 2) have real holes with different birth times. Naturally, we can find pairs of graphs (G. for which we can obtain D& * D& from vertex-color filtrations, but not from edge-color ones. Consider the graphs in Figure 4(a). The vertex-color filtration f("blue") =1.f('orange)
(''orange') = produces D = (11, (1, 20), (1,2), 2), (2, 2), (2, 2) and DD [1, oo), () oo), (2, 2). (2, 2) How- ever, there is no edge-color filtration that would tell them apart there are only two possi- ble edge-color filtrations, leading to either D= (00,00), o0), (0, 1). (0, 2), (0, 2) D', or D = (0, 20), (0, 00), (0, 1), (o, 1), (0, } = D'.
We can also show that there are graphs that can be distinguished by edge-color filtrations but not by vertex-color ones. Intuitively, one can think of this as result of edge colors being more fine-tuned. For instance. consider the graphs in Figure 4(b). We can separate these graphs using the function S(' (('orange') = 1. 1.f("blue-oranne" = 2. and f('blue') = 3. which yields D2 {(,, oo), (0, 1). (0, 1), (0, 2). (0. 2). () * ((0, oo), (0. 1), (0, 1), (0. 2), (0. 2), (0, = Dg- However, since there is no color- selarasepa set for G and G", by Theorem 1, we have that DG = De for all vertex-color filtrations. Theorem 3 formalizes the idea that none of the classes of color- based filtrations subsumes the other. In addition, Figure 4(c) illustrates that there are very simple non-isomorphic graphs that PH under both vertex- and edge-color filtrations cannot distinguish.
Theorem 3 (Edge-color vs. vertex-color filtrations). There exist non-isomorphic graphs that vertex-color filtraaton can distinguish but edge-color filtrations cannot, and vice-versa.
4 Going beyond persistent homology
We now leverage the theoretical results in Section 3 to further boost the representational capability of persistent homology. In particular, we propose modifying edge-color persistence diagrams to account for structural information that is not captured via the original diagrams. We call the resulting approach RePHINE (Refining PH by incorporating node-color into edge-based filtration). Notably, RePHINE diagrams are not only provably more expressive than standard bisor-baeed--ee ones but also make 1- dimensional topological features redundant. Additionally, we show how to integrate RePHINE into arbitrary GNN layers for graph-level prediction tasks.
Edge-color diagrams with missing holes. A major drawback of edge-color filtrations is that information about the multisets of (edge) colors is lost, i..., cannot be recovered from persistence diagrams. To reconstruct disconnecting sets, we need the edge-color permutation given by the filtration function and the number of edges- - both of which cannot be deduced from diagrams alone.
To fill this gap, we introduce the notion of missing holes. Conceptually, missing holes correspond to edges that are not associated with the disappearance of any connected component in a given filtration. By design, we set the birth time of missing holes to - this distinguishes them from real and almost holes, which have birth times equal to O. The death time of a missing hole corresponds to the first filtration step (z)) that its corresponding edge color x appears. We note that missing holes correspond to cycles obtained from 1-dim persistence diagrams.
As an example, consider the edge-color filtration in Figure 5, which produces DO (0, oo), (0, 1), (0, 2), (0, 2), (0, 4) We note that the orange edge and one of the orange-green ones do not 'kill' any 0-dim hole. This results in the missing holes (1,3) and (1,4). Clearly, missing holes bring in additional expressivity as, e.g., it would be possible distinguish graphs that only differ in the orange edge in Figure 5. Still, edge-color diagrams with missing holes are not more expressive than vertex-color ones. For instance, they cannot separate the two graphs in Figure 3(a).
Augmenting edge-color diagrams with vertex-color information. To improve the expressivity of persistent homology, simple approach is to merge tuples obtained from independent vertex- and edge-color filtrations. However, this would double the computational cost while only allowing distinguishing pairs of graphs that could already be separated by one of the filtrations. Ideally, we would like to go beyond the union of vertex- and edge-color persistence diagrams.
As in Section 3.3, we consider graphs with edge colors obtained from vertex- cooexiccoooiig functions. Also, we assume that fo and fe are independent vertex- and edge-color filtration functions, respectively. We propose adding two new elements to the tuples of edge-color diagrams with missing holes. Our augmented tuple is (b, d, 7) where and y are the additional terms. Recall that, in any edge- color filtration, Go has |V| connected components. Then, we can associate real or almost holes of edge-color diagrams with vertices in G. With this in mind, we define RePHINE diagrams follows.
7

---

G
Go
G1
C
10.1,
(0.,2.1)
(0.1.2.1)
(0..
(0,1,2.1)
(0.,
(0,12.11
(0,
RcPHINE
[0...
(o...)
(W..))
(0,4,1,8)
(0.2.1,))
00,4,1.2
(0.2,1,2)
(0,3.1.2)
diagrams
[0.r)
(e...)
(0...)
[,3,0000
(0...
(1330000
(0,4.3.4
(1,4,0.0)
Figure 5: RePHINE diagrams. At G1, one component dies and creates the almost hole (0, 2, 1). We also save that two nodes were discovered at (fourth component), with colors equal to (third component). At step 2, two other holes are killed, resulting in two tuples (0, 2, 11 2). At G3. we obtain the missing hole (1,3,0, 0, 0). Finally, G4 creates almost hole and missing hole.
Definition 3 (RePHINE diagram). The RePHINE diagram of filtration on a graph G is multiset of cardinality V + By. with elements of form (b, d, az, 7). There are two cases:
Case = O (real or almost holes). Now, b and correspond to birth and death times of a component as in edge-color filtration. We set a(w)
fo(c(w)) and ?(w) min,eN(()) fe( (e(fc(w), cv))) }), where w is the vertex that is associated with the almost or real hole. Vertices are matched with the diagram elements as follows: An almost hole (b,d) cor- responds to an edge merging two connected components, Tı, T2. Each of these connected components has exactly one vertex, WT, or WT. which has not yet been associated with any element of the RePHINE diagram. Let w arg max ( (wwr, ,"12) folc(w')) or if fu(c(wT,)) fo(c(wT,)), then sociated with real holes are vertices that have not died after the last filtration step.
arg min wr,, (ww). The vertices that
Case b (missing holes). Here, the entry d is the filtration value of an edge e that did not kill hole but produces cycle that appears at the filtration step associated with udding the edge The entries a and y take uninformative values (e.g.. 0).
Figure 5 provides an example of RePHINE diagrams. Further details of the procedure can be found in Appendix C. Notably, our scheme can be computed efficiently the same as standard persistence diagrams and is consistent we obtain identical diagrams for any two isomorphic colored graphs.
Theorem 4 (RePHINE is isomorphism invariant). Let G, G' be isomorphic graphs. Then, any edge-color and pertex-color filtrations produce identical RePHINE diagrams for G and G'.
In addition, Theorem 5 shows that RePHINE diagrams are strictly more expressive than those from both vertex- and edge-color filtrations, including O- and 1-dim topological features. Figure 4(c) provides example of graphs that cannot be recognized by any color-based filtration, but for which we can obtain distinct RePHINE diagrams.
Theorem 5 (RePHINE is strictly more expressive than color-based PH). Let D, D' be the persistence diagrams associated with any edge or vertex-color filtration of two graphs. If D', then there is a filtration that produces different RePHINN diagrams. The converse does not hold.
Despite its power, there are simple non-isomorphic graphs RePHINE cannot distinguish. In particular, two graphs have one color, RePHINE cannot separate graphs of equal size with the same number of components and cycles. For example, star and path graphs with 4 vertices of color eı produce identical RePHINE diagrams of the form & (0, d, a, d). (0, d, a, d), (0, d, a, d), (0, oo, a, d) J/. where d = (1( } and fu(c)) for arbitrary edge- and vertex-color filtration functions.
Combining RePHINE and GNNs. RePHINE diagrams can be easily incorporated into general GNN layers. For instance, one can follow the scheme in [15] to combine non- non-missing hole information with node features and leverage missing holes graph-level attributes. However, here adopt simple scheme that processes RePHINE tuples using DeepSets [38]. These topological embeddings then grouped using pooling layer and concatenated with the graph-level GNN embedding. The resulting representation fed to a feedforward network to obtain class predictions. Formally, let
(u) denote the set of neighbors of vertex in G, and h c(u) for all u e V. We compute

---

Duia
Data (-1)
cubos
cubos
cubos-
1.0
00.7
Expesoiity
Avcinyy
RePHINE
0.8
114
0.6
P91
2000
2000
2ub1002
cub10-2
cub10-2
Expresctty
8
2.00
0g
0.6
500
1000
1500
2000
500
1000
1500
2000
500
1000
1500
2000
cub12-3
cub
cub12-3
1.0
2.0
Esprestoyy
Accrny
0.7
00.
0.6
Figure 6: Average learning curves for RePHINE, PH, and GCN on connected cubic graphs. RePHINE can learn representations cases where PH and GNNs struggle to capture structural information. RePHINE shows better expressivity and fitting capability on Cub10-2 2 and Cub12-3.
GNN and RePHINE embeddings (denoted by r(0) at layer é recursively as:
1 A w (N(())) VEEV
R REPHINE f10) ( Blvv)
,00 = $600 Σ (d)
( ( (1(E-1),T1)) T((0) VUEV
dER
where f/ f(()) (i(1, 600, (t) and (PDATE are arbitrary non-linear mappings, usually im- plemented feedforward neural nets. After L layers, we obtain the combined RePHINE-GNN graph-level representation as [PoOta || PoO12((1g) Jw)]. where POOL. is either mean or concatenation, and PoOL22 is order invariant operation.
Experiments
In this section, we compare RePHINE to standard persistence diagrams from an empirical perspective. Our main goal is to evaluate whether method enables powerful graph-level representation, confirming our theoretical analysis. Therefore, we conduct two main experiments. The first one leverages an artificially created dataset, expected impose challenges to persistent homology and MP- GNNs. The second experiment aims to assess the predictive performance of RePHINE in combination with GNNs on popular benchmarks for graph classification. All methods were implemented in PyTorch [31], and our code is available at https: / / thub. com/ Aalto QuML/RePPPllt RRePHIN..
Synthetic data. We consider three datasets of cubic graphs (or 3-regular graphs): cub08, cub10, and cub12 [6]. These graphs cannot be distinguished by 1-WL and color-based PH as all vertices share the same color. Thus, we modify the datasets by changing the colors of 1, 2, or 3 vertices in each graph sample, resulting in the modified datasets cub08-1, cub10-2, and cub12-3. Also, randomly partition each dataset and create balanced binary classification task. We expect this to keep the hardness of the task while allowing some distinguishability.
We compare standard O-dim persistence diagrams from vertex-color filtrations (referred to as PH) O-dim RePHINE (i.e., no missing holes). Both approaches are processed using DeepSets with exactly the same structure and optimization procedure. Also, they operate on the original colors, not on GNN embeddings. For completeness, we report results for a 2-layer graph convolutional network (GCN) [22] followed by an MLP. We are interested in assessing if the persistence modules can overfit the observed graphs. We also monitor the methods obtain different representations for each graph, measured in terms of the proportion of unique graph embeddings over training (which we call expressivity). We provide further details and additional results with I 1-dim persistence diagrams in the supplementary material.

---

Table 1: Predictive performance on graph classification. We denote in bold the best results. For ZINC, lower is better. For most datasets, RePHINE is the best-performing method.
GNN
Diagram
NCT109 f
PROTEINS
IMDB-B
NCII
MOLHIV 1
ZINC.
76.46 1. 1.03
70.18 1 1.35
64,20 I 1.30
74,45
1 1.05
74,99 1 1.09
0,875 1. 0.009
GCN PH
77.92 +: 1.89
69.46
+: 1.83
64,80
+ 1.30
79.08
+: 1.06
73.64
: 1.29
0.513 1: 0.014
RePHINE
79.18 + 1.97
71.25
1.60
69.40
3.78
80.44
+ 0.94
75.98
1.80
0.468 +: 0.011
76.90 + 0.80
72.50
2.31
74,20 = 1.30
76.89 + 1.75
70.76 = 2.46
0.621 + 0.015
GIN PH
78.35 1: 0.68
69.46
2.48
69.80 + 0.84
79.12 + 1.23
73.37 + 4.36
0,440 + 0.019
RePHINE
79.23 + 1.67
72.32
1.89
72.80 = 2.95
80.92 + 1.92
73.71
0.91
0.411 0.015
Figure 6 shows the learning curves for 2000 epochs, averaged over five runs. Notably, for all datasets, the expressivity of RePHINE is significantly higher than those from PH and similar to GNN's. On cub10-2, while PH and GNN obtain accuracies of around 0.5, RePHINE allows better fit to the observed data, illustrated by higher accuracy and lower loss values.
Real-world data. To assess the performance of RePHINE on real data, we use six popular datasets for graph classification (details in the Supplementary): PROTEINS, IMDB-BINARY, NCI1, NC1109, MOLHIV and ZINC [7. 16. 20]. We compare RePHINE against standard vertex-color persistence diagrams (simply called PH here). Again, we do not aim to benehmark the performance of topological GNNs, but isolate the effect of the persistence modules. Thus, we adopt default (shallow) GNN architectures and process the persistence diagrams exactly the same way using DeepSets. We report the mean and standard deviation of predictive metrics (AUC for MOLHIV, MAE for ZINC, and Accuracy for the remaining) over five runs. We provide further implementation details in Appendix C.
Table shows the results of PH and RePHINE combined with GCN [22] and GIN [37] models. Notably, RePHINE consistently outperforms PH, being the best-performing method in out of 12 experiments. Overall, we note that GIN-based approaches achieve slightly better results. Our results suggest that RcPHINE should be the default choice for persistence descriptors on graphs.
Table 2: PersLay vs. RePHINE: Accuracy results on graph classification.
Method
NCI109
PROTEINS
IMDB-B
NCI1
PersLay
70.12 + 0.83
67.68
+ 1.94
68.60 = 5.13
68.86 + 0.86
RePHINE+Linear
73.27 1.69
71.96
1.85
70.40 2.97
74.94 = 1.35
Comparison to PersLay [2]. We also compare our method against another topological neural network, namely, PersLay. Since PersLay does not leverage GNNs, we adapted our initial design for a fair comparison. Specifically, we compute RePHINE diagrams with learned filtration functions and apply a linear classifier to provide class predictions. Also, we concatenate the vectorial representations of the RePHINE diagrams with the same graph-level features obtained using PersLay. We refer to our variant RePHINE-Linear, Table 2 reports accuracy results over 5 runs on 4 datasets. For all datasets, RePHINE+Linear achieves higher accuracy, with a significant margin overall.
6 Conclusion, Broader Impact, and Limitations
We resolve the expressivity of persistent homology methods for graph representation learning, establishing complete characterization of attributed graphs that can be distinguished with general node- and edge-color filtrations. Central our analyses is a novel notion of color-separating sets.
Much like how WL test has fostered more expressive graph neural networks (GNNs), our framework of color-separating sets enables the design of provably more powerful topological descriptors such as RePHINE (introduced here). RePHINE is computationally efficient and can be readily integrated into GNNs, yielding empirical gains on several real benchmarks.
We have not analyzed here other types of filtrations, e.g., those based on the spectral decomposition of graph Laplacians. Future work should also analyze the stability, generalization capabilities, and local versions of RePHINE. Overall, we expect this work to spur principled methods that can leverage both topological and geometric information, e.g., to obtain richer representations for molecules in applications such as drug discovery and material design.
10

---

Acknowledgmentt
This work was supported by Academy of Finland (Flagship programme: Finnish Center for Artificial Intelligence FCAI) and a tenure-track starting grant by Aalto University. We also acknowledge the computational resources provided by the Aalto Science-IT Project from Computer Science IT. We are grateful to the anonymous area chair and reviewers for their constructive feedback. Johanna Immonen thanks Tuan Anh Pham, Jannis Halbey, Negar Soltan Mohammadi, Yunseon (Sunnie) Lee, Bruce Nguyen and Nahal Mirzaie for their support and for all the fun during her research internship at Aalto University in the summer of 2022.
References
[1] P. Barceló, E. V. Kostylev, M. Monet, Pérez, J. L.. Reutter, and J.PP. Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations (ICLR), 2020.
[2] M. Carrière, F. Chazal, Y. lke, T. Lacombe, M. Royer, and Y. Umeda. PersLay: A neural network layer for persistence diagrams and new graph topological signatures. In International Conference on Artificial Intelligence and Statisties (AISTATS), 2020.
[3] M. Carriere, F, Chazal, M. Glisse, lke, H. Kannan, and Umeda. Optimizing persistent homology based functions. In International Conference on Machine Learning (ICML), 2021.
[4] Y. Chen, B. Coskunuzer, and Y. Gel. Topological relational learning on graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[5] D. Cohen-Steiner, H. Edelsbrunner, and Harer. Stability of persistence diagrams. In Proceedings of the Twenty-Fitt Crentty-irsttaa Annual Symposium on Computational Geometry, 2005.
[6] K. Coolsact, S. D'hondt, and J. Goedgebeur, House of graphs 2.0: A database of interesting graphs and more. Discrete Applied Mathematics, 325:97-107, 2023.
[7] V. P. Dwivedi, C. K. Joshi, A. T. Lau, T. Laurent, Y. Bengio, and X. Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43): 18, 2023.
[8] Edelsbrunner, Letscher, and Zomorodian. Topological persistence and simplification.. Discrete & Compu- tational Geometry, 28(4), 2002.
[9] H. Edelsbrunner and J. Harer. Computational Topology Introduction. American Mathematical Society, 2010.
[10] M. Fey and Lenssen. Fast graph representation learning with PyTorch Geometric. Workshop track of the International Conference on Representation Learning (ICLR), 2019.
[11] V. Garg, S. Jegelka, and T. Jaakkola. Generalization and representational limits of graph neural networks. In International Conference Machine Learning (ICML), 2020.
[12] C. Hofer, Kwitt, M. Niethammer. and A. Uhl. Deep learning with topological signatures. Advances in Neural Information Processing Systems (NeurIPS), 2017.
[13] C. Hofer, F. Graf, B. Rieck, M. Niethammer, and R. Kwitt. Graph filtration learning. In International Conference on Machine Learning (ICML), 2020.
[14] C. D. Hofer, R. Kwitt, and M. Niethammer. Learning representations of persistence barcodes. Journal of Machine Learning Research, 20(126):1 145, 2019.
[15] M. Horn, E. De Brouwer, M. Moor, Y. Moreau, B. Rieck, and K. Borgwardt. Topological graph neural networks. In International Conference on Learning Representations (ICLR), 2022.
[16] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovee. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687, 2020.
[17] Xiaoling Hu, Fuxin Li, Dimitris Samaras, and Chao Chen. Topology-preservingg deep image segmentation. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[18] S. loffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference Machine Learning (ICML), 2015.
11

---

[19] John J. Irwin, Teague Sterling, Michael M. Mysinger, Erin S. Bolstad, and Ryan G. Coleman. Zinc: A free tool to discover chemistry for biology. Journal of Chemical Information and Modeling, 52(7):1757-1768. 2012.
[20] Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Benchmark data sets for graph kernels, 2016. URL http://grrphkkernellle cs. tu-dur tmund. de.
[21] D. Kingma and Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
[22] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
[23] V. Kovacev-Nikolic, P. Bubenik, D. Nikolić, and G. Heo. Using persistent homology and dynamical distances analyze protein binding. Statistical Applications in Genetics and Molecular Biology, 15(1): 19-38, 2016.
[24] Kramár, Levanger, Tithof, Suri, M. Xu, Paul, M. Schatz, and K. Mischaikow. Analysis of Kolmogorov flow and Rayleigh-Bénar convection using persistent homology. Physica D: Nonlinear Phenomena, 334:82-90 28229998222 2016.
[25] Y. Lee, S. D. Barthel, P. Dlotko, S. M. Moosavi, K. Hess, and B. Smit. Quantifying similarity of pore-geometry in nanoporous materials. Nature Communications, 8(1). 2017.
[26] J. Leygonie, S. Oudot, and U. Tillmann. A framework for differential calculus on persistence barcodes. Foundations of Computational Mathematics, 22(())1069 108699--131 1131, 2022.
[27] C. Li, M. Ovsjanikov, and E. Chazal. Persistence- based structural recognition. In IEEE Conference on Computer Vision and Puttern Recognition (CVPR), 2014.
[28] A. Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Reprexentations (ICLR), 2020.
[29] A. Loukas. How hard is to distinguish graphs with graph neural networks? In Advances in Neurul Information Processing Systems (NeurIPS), 2020.
[30] C. Morris, M. Ritzert, M. Foy, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAI Conference Artificial Intelligence (AAAI), 2019.
[31] A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, 7. DeVioo, Z. Lin, A. Desmaison, L., Antiga, and A. Lerer. Automatic differentiation in pytorch. In Advances in Neural Information Processing Systems (NeurIPS Workshop). 2017.
[32] B. Rieck. On the expressivity of persistent homology in graph learning. arXiv: 2302.09826, 2023.
[33] B. Rieck, C. Bock, and K. Borgwardt. A persistent weisfeiler-lehman procedure for graph classification. In International Conference Machine Learning (ICML), 2019.
[34] R. Sato. A survey on the expressive power of graph neural networks. arXiv:2003.04077 2020.
[35] R. Sato, M. Yamada, and H. Kashima. Approximation ratios of graph neural networks for combinatorial problems. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[36] B. Weisfeiler and A. A. Lehman, A reduction of graph to a canonical form and an algebra arising during this reduction. Neuchnn--Technicheskay Informatsia, 229):22-16, 1968.
[37] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019.
[38] M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R. Salakhutdinov, and A. Smola. Deep sets. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
[39] Q Zhao and Y. Wang. Learning metrics for persistence-based summaries and applications for graph classification. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[40] Q. Zhao, Z. Ye, C. Chen, and Y. Wang. Persistence enhanced graph neural network. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
12

---

Supplementary material: Going beyond persistent homology using persistent homology
A Persistent homology
Persistent homology (PH) is of the workhorses for topological data analysis (TDA). A cen- tral idea underlying PH is to investigate the multiresolution structure in data through the lens of low-dimensional topological features such as connected components (0-dimensional), loops (1- dimensional), and voids (2-dimensional), Here, we provide brief description of PH, and how it extends to graphs. In particular, we do present proofs and do not show that the constructions well-defined. For detailed treatment, we refer the reader to [13], [9].
We will first define homological groups. They allow characterise p-dimensional holes in topological space such as a simplicial complex. We present the theory for simplicial complexes, as focus is 1-dimensional simplicial complexes (i.e. graphs).
Let K be a simplicial complex. The p-chains are formal sums c= Σ agas, where a; E Z.22 and a; are p-simplices in K. One can think of p-chain with componentwise addition, p-chains form the group (K))
set of p-simplices such that a; = 1. Together
Now, consider simplex a = (vo ... Up) E K. We can define boundary for by
0po
(Vo,..., ..., U/+1, Up),
==0
i.e., 0po is a sum of the (p- -idieensional faces of a. We can extend this to define boundary homomorphism op Cp(K) + Cp-1(K) where 0g Ea,or a,000 Thus, we can define
sequence of groups
...Cp+ (K) Bpti, Cp(K) 3 CK-1(K)..,
each connected with boundary homomorphism. This sequence chain complex, and is the last definition we need in order to consider homology groups
The pth homology group is a group of p-chains with empty boundary (i.e. 0,0 0) such that each of these particular p-chains (cycles) are a boundary of a different simplex in Cp-1 So, we can define the homology group the quotient space
H kerō,, /mm0
The rank of H, is equal to the yth Betti number (3p). Then, let us see how the homology groups can be refined to gain persistent homology groups
Persistent homology tracks the evolution of Betri numbers in a sequence of chain complexes. For this, need filtration, which an increasing sequence of simplicial complexes (FF) such that F. = C F2 .... F, K. By constructing all homology groups for each of these simplicial complexes, we can capture changes. New holes (or, homology classes) may emerge, or they may be annihilated such that only the older remains. As such, we can associate pair of timestamps, or persistence points. (i, for every hole indicate the filtration steps appeared and disappeared. The persistence of point (i,j) is the duration for which the corresponding feature was in existence, ie.. the difference j|- We set = oo if the hole does not disappear, i.e. is present at the last filtration step. The extension to persistent homology groups and persistent Betti numbers is natural:
H kerθ,/ (Im0( O kerê,),

---

and the pth persistent Betri number 3 are given by the rank of H.d as earlier. Lastly, persistent diagram that consists of the persistent points (i,j) with multiplicities
Hp -
1,j-1 (0p-1.3-1 -
(3p
())
where i < j. encodes the persistent homology groups entirely by the Fundamental Lemma of Persistent Homology.
For graphs, the filtration may viewed as creating an increasing sequence of subgraphs. This entails selecting subset of vertices and edges of the graph at each step of the filtration. One leam parameterized function f (e.g., a neural network) to assign some value to each a E K, and thereby select the subsets K, based sequence (os) such that on 2 02 2... 2 Ox;:
threshold 0; R. That is, induces filtration (Fi)=z using
F F=F(faa) for K f(o) 2 a.).
We provide a detailed pseudocode in Algorithm to compute the persistence diagram for an input graph. The algorithm uses the Union-Find data structure, also known disjoint-set forest. The code assumes we are given vertex-cold filter values, stored in the variable vValues. The algorithm returns a multiset containing 0- and I-dimensional persistence tuples (i.e., persistence diagrams).
Algorithm 1 Computing persistence diagrams
Require: V, E, Values
Vertices, edges, and vertex-color filter values
uf < UNIONFIND( V V 2)
persO <- zcros
b Initialize the persistence tuples
persl < zcros 2)
for E E do
(u, w) <- e
eValues[e] <- max((Values(oo) vValues(w))
end for persO[:, 1] Values SINDICES, SVALUES + SoRr(eValues)
>> Pre-set the "birth' times for e, weight E Sair(SSNDICES,SVALLEEE do > Pair equivalent to the zip function in Python younger denotes the component that will die
w) <
younger ff.)in(())
older < uf.find(w)
younger older then
A cycle detected
pers l(e, [, 1] 4- weight
pers 2]
continue
else
if v VValues[younger] < Valuessolderr] then
younger, older, u, +- older, younger, w,
end if
end if
persOfyounger, 2] + weight
uf.merge(v, w)
Merge two connected components
end for
for E uf.rrots() do
persO[r, 2] +-
end for
D, +- JOIN pers
return D.
14

---

B Proofs
B.1 Proof of Lemma 1: Vertex- baste filtrations can generate inconsistent diagrams
Figure S1: Filtrations induced by injective vertex filter functions for two isomorphic graphs. Node ids are used as filter function. The top-row filtration induces the persistence diagram DP (2. (3, 3), (4. 4), (5, 5), (6, G) while the second-row filtration produces D2 (2. (4,4)) (5, (6, ().
Proof. Consider a simple cyclic graph with 6 vertices that share the same color. Since the vertices are structurally identical and have the same color, would expect to get single persistence diagram irrespective of the labeling of the vertices. However, this is not the case. Consider two different labelings for the vertices the graph: & (#1, U2, V3, 14. Ub (6) and &g (U1, U4, U2, 06 v3,25) (see Figure S1). Now, consider an injective vertex -hatex filtration where f (m;) > (1,) if j. Then, obtain two different persistence diagrams, D2 (1, oo), (2, (3, 3), (4, (5, 5), 6)} and
D2 = (1, oo), (2, 4), (3, 5), (4, 4). (5,5), (6, 6) H- We note that for any choice of certex-based injective filter function on this cycle graph, can follow similar procedure build two different
labelings such that the persistence diagrams are different.
B.2 Proof of Lemma 2: Equivalence between component-wise colors and real holes
Proof. We consider two arbitrary graphs G = (V. E, c, X) and G' = (V", E', é, X') and an injective filter function X X R. We note that if G and G' do have the same number of connected components (i.c., g * Bg.). then G and G' differ on the number of real holes, i.e., their multisets of real holes are different trivially. Thus, we now assume 38 B8 have same colors- if there is a color in G that is not in G', the claim is trivial.
We also assume both graphs
[+] Recall that X, = {c(v) v E Vc.} denotes the set colors in the component C, C. Similarly, X is the set of colors C/ S G'. We want to show that if [ {X * HX/D then there exists a filtration such that the multisets of real holes are different. We proceed with proof by induction on the number of colors.
If there is only 1 color, component-wise colors cannot differ for graphs with 08 =88.. Let us thus consider colors (say, and w). For colors, there are only three possibilities for what XA E { {X; | may be: [b), {w} or (). Now, let us denote the multiplicities of (b), {w) and {b. () in (X: 1= by n1, and na, respectively. Note that for G and G' with 88 gg. we have a1 + + ns n + ná + nég. Thus, when ( + X there are four cases to consider:
mi + wh, ne # n²2, ng = n/z: Here, n2 + ng + n22 + nl correspond multiplicities of real holes (w, oo) for G and G" respectively, in filtration that introduces the color w first.
2. nı * nh, n2 = nly n3 # nls Again, n2 + na + nly + n's correspond to multiplicities of real holes (w, 2o) for G and G" respectively in filtration that introduces the color w first.
3. n, = =n', n2 # nly, nag # n/z Now, n, +ng # n + nty correspond to multiplicities real holes (b, oo) for G and G' respectively in filtration that introduces the color b first.
4. # nh, n2 # nly, na # n/z: Similarly, b1 + n3 * n1 + n's correspond to multiplicities of filtration that introduces the color first.
real holes (b, oo) for and G respectively
Note that cases as ny # n/,, n2 T2g n2 níg are not possible as 1n + + ny = n²i + n22 + r2/-
Let us then assume that there are colors, and there exists permutation of the colors (c1, C2. .... Ct that induces filtration giving different colored representatives.
15

---

Let us consider graphs G and G' with / + colors. Now, if ( * { for subgraphs of G and G' with only colors, the permutation {c++1. C12 C2. Ct induces a filtration where the representatives of first I colors differ (and there may or may not be a difference also in the representatives of the + 1-th color). However, there are no such subgraphs, this means that each of the pairs of unmatched component-colors contain the 1 + 1 th color. Now {cI, ..., C, Q++1) must induce the wanted kind filtration, since now the representatives of each component are as in I colors. The claim follows by the induction principle.
[+] Now. we want to prove that if there is filtration such that the multisets of real holes differ, then {x + B. We proceed with a proof by contrapositive.
Assume that [X = {x;B. Recall that, for a filter f. the color of the representatives of a real hole associated with C, is given by arg min f(x) If if {X; Hf {X: it implies that the multisets of colors of the representatives are identical. Finally, note that the birth times of real holes are functions of these colors and, therefore, identical well.
B.3 Proof of Lemma 3: Almost holes and separating sets
Statement 1: We want to show that if (f(x)(1), f(x(1)) is an almost hole, then S = {u E V[f(c(v)) 2 ((x(1)) is a separating set of G = E,,,
22
U'
Proof. Let d = (f(x(t)), f(x(()) be an almost hole. Then, we know there is at least one vertex w of color c(w)= = (b)) that gives birth to new connected component the filtration step G [(:00)) Also, there is distinct vertex w' such that w and w' are not in the same component at G (((t)) but are connected at G f(ultty- The existence of w' is guaranteed since if there was no such w' that gets connected to w at G G(zzt))) d would be real hole, or if w was connected to all other nodes at G (() d would be a trivial hole. Figure S2 illustrates filtration on a 5-vertex graph with colors. The filtration produces the persistence diagram (11, oo), (2, 2). (3, 4), (4, 4), (5, 5)ß. with single almost hole (3, 4). According to our description, w corresponds to 03 (with (b) 'grey' and (() = 3), and could be a candidate to w', for instance.
U/
Figure S2: Graph to help illustrate the connectivity of almost holes.
The discovery of the vertices T fu E f(c(v)) = (a)( connects w to w/ since this set added the step when the component associated with w dies at f(x(()). Equivalently, T is separating set of G f((())- However, we want a separating set of G (not of G ((ato))) Finally, we note
that expanding T to S = (u E V f(v) 2 f(x(1)) suffices to obtain separating set of G.
Let S be a separating set of G that splits a connected component C C G into k components C1, if the set of colors of vertices in U Ve, is disjoint from those of the remaining vertices, i.e., {c(v) UE U (c(v) - Vo. =
Statement 2:
Ct. Then, there exists filtration that produces k almost holes
Proof. Let us denote by C1, C2 ... Ck the connected components that S separates C' into. We can first set restriction of flut,,ve Vo, be any function mapping vertex colors to f1,2, U Vc,1l ie., vertices in _ must take filtration values in {1, .... U Vc,1). Similarly, can set flewu, Ve, to be any function to {1 - Vo, + 1,... [V]].
The function of obtained by combining the domains of flut ve, and fly Vo, is well defined v - = 0. Since Cr C2
due to the assumption {a(v) | v E V C2 are not path-connected, the persistence diagram induced by f must have k holes that are born at filtration steps in {1,2,... U V. Also, since the vertices of S are added at filtration steps in {I { Vc, + 11 1,..., [V]], all holes die, forcing the birth and death times to be different. Thus, there must be one real hole corresponding to the connected component C' and f almost holes. L
16

---

B.4 Proof of Lemma 4: Distinct almost holes imply distinct color-separating sets
Proof. We will consider two cases. The first one assumes that the multisets of real holes of Dg and De are different. In the second case, we consider identical multisets of real holes and different multisets of almost holes.
Case I: multisets of real holes differ. By Lemma have that the graphs have distinct component- wise colors- - that is, an empty set is a color-separating set.
Case 2: D& and D& have identical real holes, but different multisets of almost holes. We want to show that there is a color-separating set for G and G". We note that we can split the condition of distinct multisets of almost holes into two sub-cases: (i) There is some color zo such that there are more almost holes with birth time fzx) in D& than in De (ii) There is some color zo such that there are more almost holes with death / (200 in Dg than in Dg.-
Let us first consider case (i). By the definition of birth time, we have that G((z)) has more connected components of color set {mo} than G G'(())) As such, fo E X (U)((())) > f(x)) is color- separating set for G and G'.
For case (ii), assume that there equally many births of almost holes associated the the color To - otherwise we return to case (i), for which we showed how to build a color-separating set. We note that if there is a different number of connected components any earlier filtration step than when En is introduced (i.e. f < (Io)), then {a E X U X' > f(y)} is a color separating set since G()) and (oy) do not have as many connected components, they cannot have identical component-wise colors. However, if there is no such filtration step fvy, it follows that G (=x)) and G' ((zo) cannot have the same number of components. This follows since vertices of color 2g kill more connected components in G G(z)) than in G ((zz)) while prior to this, the numbers of components were equal. Therefore, {z E X XXX)(((=) f(xo)} is color-separating set.
B.5 Proof of Lemma 5: Equivalence between birth times and vertex colors
Proof. We consider graph G = (V, E, X) and any injective vertex-color filter f X - R from which we obtain persistence diagram DD, We want to show that there exists a bijection between the multiset of birth times B = {bb (b, d) E D and the multiset of vertex colors X (c(v) | E V B. Note that can also represent multiset the distinct elements of B, and my Sg + N is a multiplicity function that gives the number of occurrences of each element of Sg in the multiset. If there is a bijection g SB - Sx such that mg = mx o g. then we say that is also a bijection between the multisets B and X.
pair B = (Sg, mg) where Sg is set comprising
We note that Sx Im[c] denotes the set of distinet colors in G. Without loss of generality, since we are interested in filtrations induced by f on G. we can constrain ourselves to filter values on Sx- Thus, filtrations induced by f Sx - R are increasing (i.e., for any consecutive filtration steps j > i, we have that Vú V4 * 9) and produce filtration steps T = {f()) 2 E Sx}. ). Because such filtrations are increasing, we have least one vertex discovered at each step, resulting in the set of distinct birth times SB- 'T The mapping g Sx + Ss where g(x) f(x) for all x E Sx is a bijection. By definition, the number of vertices discovered at step fxx equals the number of persistence pairs with birth time fx), which is also equal to the number of vertices of color æ. This implies that the multiplicity of an element æ in X is the same as its corresponding element g(x) in B.
B.6 Proof of Theorem 1: The expressive power of vertex-color filtrations
Proof. We consider graphs G = (V, F. X) and G¹ F'','' and adopt the following notation. We use X' = (c(u) v E V and X" [ VVE to denote the multisets of vertex colors of G and G". Also, we denote by Ct...., Cs the components of G, and by Ci..... C. the components of G'. The set X; = (c(w) w E Vc, ) denotes the distinct colors appearing in C.. Similarly, X = {d' w E Vo refers to the distinct colors in C%
[Forward direction +] D4 + Da + there is a color-separating set
The persistence diagrams Dog and Do. for graphs with X' = X" have the same birth times. implies that if both the real holes and almost holes are identical, then the diagrams are also identical. As such,
17

---

the assumption that D& # Dé gives that either (1) their multisets of real holes or (2) their multiset of almost holes are different. In the following, we consider these two cases.
Regarding case (1), Lemma 2 gives that if D # D& with different multisets of real holes, then [= * { Whenever this happens, the forward direction holds as even an empty set would work as a color-separating set here. Thus, it suffices to consider the case when D and De only differ in their multisets of almost holes. In this case, we can directly leverage Lemma 4 to obtain that there a color-separating set for G and G".
we have that &.K:Be=
[Backward direction = Now we want to show that there is a color-separating set Q * @ for G and G", there exists filtration such that D8 * D
If I = 0. i.e. G and G' have distinct component-wil and D& having different multisets of real holes. If Q A 0. we can however use Lemma 2 subgraphs Gp and Gyp, induced by V V \ {w V c(w) E Q} and V V \ fw V c'(w) Q} to gain a filter function 9 such that the diagrams for these subgraphs differ. Now, let's choose any a filter function such that fax) g(x) V> E X Q AND the filtration values for vertices with colors in X \. Q are smaller than those with colors in Q. It follows there is a filtration step j such that Gj = Gp and G¹ G.p.. and that the birth times for real holes (if the vertices of colors in Q do not merge the real holes of the subgraphs) or almost holes (if the vertices of colors in Q do merge
colors, the claim follows by Lemma 2, with D8
components that would have been real holes in the subgraphs) differ. Thus, D f D
B.7 Proof of Lemma 6: Edge-based almost holes as disconnecting sets
Proof. Initially, when none of the edges are added, there must be V connected components. By definition, each pair (0, d) E 'D' corresponds to the death of one component. It follows that G ((zto)
has c = | (().d) E 'D0 d S (xx(1) connected components. components, the subgraph with vertices V and edges E \ fe E E f(((e) 2 fxx(1)) has more than go connected components. Thus, fe E E f(((e)) 2 f(x(d)) is a disconnecting set of G. A
G has 3 connected
B.8 Lemma 7: The reconstruction of disconnecting set
Proof. Let π be the permutation of colors associated with a vertex-color filter function ʃ. i.e., for a set of colors X = (21...., Em), we have that fII(() < f(*+(+))) A i 1...., m 1. Also, assume the colors associated with disconnecting set S of a graph G = EV, X) is Xs = {>*(()) (+++1) ................................ (ar()))
If S is minimal disconnecting set, (0, (x))))) must be an almost hole in D since if we could add edges W S with color (R) without killing some connected component of G ((*( the set of edges S' = 5S \ W would form a proper disconnecting subset of a minimal disconnecting set If S is not minimal disconnecting, then there must be a proper subset S C S that is minimal disconnecting set of G. Now, we choose S' to be included first in the filtration, followed by elements of S S'. Thus, in both cases, there is filtration s.t. an almost-hole (0, f(xx) appears, which allows us to reconstruct S.
B.9 Proof of Theorem 2: The expressive power of edge-color filtrations [=] We split the proof of the backward direction into three cases.
Proof. Case 1: The color-disconnecting set Q equals to X U X'. This is trivial case. If Q U X', G and G' have distinct number of connected components when all the edges are removed from both graphs. This means V * VV). Now, if [V| * [V']. then [Dg| * IDg for any filtration.
Case 2: The color-disconnecting set Q is an empty set. Now, the graphs have distinct number of connected component (even if none of the edges are removed), i.e. 38 + BQ.. The diagrams differ for any filtration since they have different numbers of real holes.
Case The color-disconnecting set Q + 0 is a proper subset of X U X': The existence of a color-disconnecting set implies there is a set S c X U X' such that by removing the edges of colors S, the two graphs will have different number of connected components. Without loss of generality, we can assume that after removing the edges of colors S, G has more components than G'. Now,
18

---

we note that in a filtration where the colors of S are added the latest, there must either be more almost holes (0. ())()) in Dg than in & with 2(() E S. or alternatively g # P In both cases, D& # or for some filter function f.
[=] To prove the forward direction of the Theorem, we consider the cases where the edge-color diagrams differ in 1) their size, 2) the number of real holes, and 3) their almost holes.
Proof. Case I: |Del * DD Again, this corresponds to a trivial case, since if |Dal * |Dor), then [V] + |V'. Now, Q X X' is color-discomnecting set.
Case 2: Da and De differ in their real holes. If there is a different count of real holes, then 98 * .g., and Q 9 is a calloriisoonnetting set.
Case 3: De and Da only differ in their almost holes. We now assume that |Pal = [P and 08 = but De + Der This means that there is some (0,d) 'D such that there are more almost holes with this death time in DG than in De' without loss of generality. There may be several such almost holes (for which the diagrams differ) with distinct death times. Let's denote the set of the death times for these almost holes by D. Then, let dman be the minimum of the death times in D, iee dmmi minge D d. Let us show that the set Q = {ar X U X' f() > dmain } disconnects G' into more connected components than G. For any lower filtration step, the induced subgraphs must have as many connected components because the almost holes corresponding to those steps match, and [Dal [. i.e. [V] |V', which means that at filtration step O, we begin with equally many connected components. At filtration step dmmin we connect more components in G than in G' because there are more almost holes corresponding to this step in De than in Der. Now, Q must be color-disconnecting set.
B.10 Proof of Theorem 3: Edge-color vs. vertex-color filtrations
Proof. This Theorem is proved in Section 3.3. In particular, Figure 3(a) provides an example of pairs of graphs that can be distinguished by vertex-color filtrations but not from edge-color ones. On the other hand, the graphs in Figure 3(b) can be distinguished by edge-color filtrations but not from vertex-color ones. This concludes the proof.
B.11 Proof of Theorem 4: RePHINE is isomorphism invariant
Proof. RePHINE diagram's isomorphism invariance stems from the fact that it is a function of a filtration on graph, and this filtration is gained from isomorphism invariant colorings. If this assumption is violated and the colorings are not gained in an invariant way, RePHINE diagrams can also be inconsistent.
It is easy to check that the tuples (b,d) are isomorphism invariant when b = O, these tuples correspond to diagrams gained from edge-color filtration. In this case, we can check the conditions given by Theorem 2 and note none of the conditions may be met with isomorphic graphs. With regard to the set of missing holes is multiset of edge colors that did not appear in edge-color filtration diagram. This set can thus be gained by considering the multiset of edge colours and the edge-color diagram, which are both isomorphism invariant.
Further, it is also easy to see that the tuples (a, 7)) are invariant. When b 0. the set of a's corresponds to the multiset of vertex colours, and for each vertex, m(n) fc fe(((())
However, the crucial part is how these two tuples are concatenated, i.e., how each of the vertices are associated with real and almost-holes. In particular, we need to check when two connected components are merged at filtration step i and RePHINE compares the representatives (i.e. vertices of a connected component which have not yet 'died') of the two components, we will end up with same diagram elements of form (6, i, a, 7) regardless of the order we add the edges of color with filtration value i. In other words, while the RePHINE algorithm considers one edge at time and does only pairwise comparisons between merged connected components, the order or these comparisons must not affect the decision on which vertices are associated with death time i. Let's consider what happens when adding all the edges of color results in merging more than two components. Assume there is new connected components constituting of old connected components Ti, T..,.... T,. Now, there are two different cases. Assume first that there a strict minimum among the vertex filtration values of the old representatives. Then, any pairwise comparison will lead to choosing this minimum
19

---

as the representative of the new connected component and all the other vertices will die at this filtration step. Then, assume there is no strict minimum but tie between two or more representatives. Then, there will be comparisons based on % but choosing maximum of these is also permutation invariant function, In case there are two (or more) representatives such that there a tie based on the vertex filtration values and y values, choosing at random any of these leads to the same diagram. Lastly, note that for each real hole, (6, d) = (0, 20), and so it does not thus matter how each of the vertices are matched to the real holes, when rest of vertices are associated with almost-holes in an invariant way.
B.12 Proof of Theorem 5: RePHINE is strictly more expressive than color-based PH
Let Ra denote the RePHINE diagram for a graph G. Similarly, let D..c and De,G denote persistence diagrams associated with vertex- and edge-color filtrations of G. We assume that D.,G (D Pi.g) and De.G = (D De,g) include 0- and 1-dim persistence diagrams. We want to show that for two graphs G and G"
(i) if there is vertex-color filtration such that Du, + Du,rr then there is a filtration that lead RR f Roy
(ii) if there is edge-color filtration such that De,G # De,cr then there is a filtration that lead to RG * Ro.
These results would show that RePHINE is at least as expressive as color-based persistence diagrams. We further show that
(iii) there is pair of non-isomorphic graphs for which can obtain Ro # Roy but D., Du,cy and De,G = =De.G' for all vertex- and edge-color filtrations.
Proof. Part (i): DO,G # Du,G + RR # Ro. Let f be the vertex-color function associated with the standard diagrams D. We can choose the RePHINE's vertex-level function fo such that f = f. We note that the original diagrams can be obtained from an auxiliary edge-level filter function fo where fa(u, w) mn f((ww)) The procedure is described in Algorithm 1.
Let fe be the edge-color filter function of RePHINE. If we choose fe = fa. then RePHINE contains in the second and third elements of its tuples exactly the same persistence information of the vertex-color diagrams. Note that in this case, we do not even need to require injectivity of the edge-color filter fe since the max function is not injective. Regarding the 1-dim features, for any tuple (d, oo) in the 1-dim persistence diagram, we have a missing hole (1, d, .) that comprises the same information. Thus, we have constructed vertex- and edge-color functions such that D.,G + De,G' Ra # Ray
Part (ii): De.G * De,G + Rs + Ro. This is trivial case as RePHINE consists of an augmented version of standard edge-color diagrams. Let f be the edge-color (injective) filter function associated with the standard diagrams. In this case, we can simply set fo = f. where fo is RePHINE's edge-color filter. Then, the first and second elements of RePHINE's tuples correspond to D... Regarding the 1-dim features, the only difference is the way the information is encoded. While we adopted the convention (1, d) for missing holes, the standard diagrams often use (d, oo). The relevant information is the same. Therefore, RePHINE is at least as expressive as edge-color persistence diagrams.
Part (iii). To show that RePHINE strictly more expressive than based PH. it suffices to provide example of two graphs for which there is filtration such that Rg * Ro but these graphs cannot be separated from any vertex- or edge-color filtration. We use the pair of graphs in Figure 3(c). We note that these graphs have cycles, making 1-dim persistence information trivial.
We first note that their multisets of colors are identical and there is no color-separating sets for these two graphs - i... there is no subset of colors whose removal would separate the graphs into distinct component-wise colors. Thus, by Theorem 1, there is no vertex-color filtration s.t. De,G F De,G'
Also, we have that |V|= [V'| and X = X' and 8g pg and there is no color-disconnecting set for G and G' (i.e., there is no edge colors whose removal would generate subgraphs with different number of components). By Theorem 2, these graphs cannot be separated by any edge-color filtration.
However, if we choose the filter functions fu = 1, Jo.(orange") = 2, fe b'lue- 4, and fe( o'bbbu)-oraagge"
3. we obtain distinct RePHINE di-
20

---

agrams given by Rg = [(0,4, (0, xc, 1.3), (0,33,.)) (0, (0, 4, (0.3,,2)) (0,3,,,))
and Ro
C
Implementation details
C.1
Datasets
Table S1 reports summary statistics of the real-world datasets used in this paper. For the IMDB-B dataset, we use uninformative features (vector ones) for all nodes. NCII, NCI109, Proteins, and IMDB-B are part of the TU Datasets", vast collection of datasets commonly used for evaluating graph kernel methods and GNNs. MOLHIV is the largest dataset (over 41K graphs) and is part of the Open Graph Benchmark We also consider regression task using the ZINC dataset subset of the popular ZINC-2500 chemical compounds [19], which is particularly suitable for molecular property prediction [7].
Table S1: Statistics of the datasets.
Dataset
#graphs
#classes
#node labels
Avg #nodes
Avg #edges
NCII
4110
2
37
29.87
32.30
IMDB-B
1000
2
19.77
96.53
PROTHINS (full)
1113
2
3
39.06
72.82
NC1109
4127
2
38
29.68
32.13
MOLHIV
41127
2
9
25.5
27.5
ZINC
12000
28
23.16
49.83
The cubic datasets (CubicO8, Cubic10, and Cubic12) comprise non-isomorphic 3-regular graphs with 8, 10, and 12 vertices, respectively. These datasets contain 5 (Cubic08), 19 (Cubic10), and 85 (Cubic12) graphs and can be downloaded at https: https::/ htt/hhousooggrpppppeeo cubic. For each dataset, we create balanced graph classification problem by randomly assigning each graph a binary class. Also, since the graphs do not have node features, we add a scalar feature to each vertex, i.c., e(v) for all However, this would make IWL-GNNs and PH fail distinguish any pair of graphs. Thus, we change the features of some arbitrary vertices each graph, making c(v>) = 1 for vertex in graphs from Cubi c08, 2 vertices in Cubi c10, and 3 vertices in Cubic12 we denote the resulting datasets as Cubic08-1 Cubic10-2, and Cubic12-3. Given the modified datasets, we aim to assess if the existing methods can overfit (correctly classify all) the samples.
org/
C.2 Models
We implement all models using the PyTorch Geometric Library [10].
Synthetic data. The GNN architecture consists of a GCN with 2 convolutional layers followed by readout layer and an MLP (one hidden layer) with ReLU activation. The resulting architecture is: Conv (1, 36) + Conv (36, 16) + sum sum-readout - BN (16) + MLP (16, 24, 1), where BN denotes batch norm layer [18]. For the PH model, we consider standard vertex-color filtration functions. In particular, we apply the same procedure as Hofer et al. [13], Horn et al. [15] to compute the persistence tuples. We only consider 0-dim persistence diagrams. The filtration function consists of an MLP with 8 hidden units and ReLU activation followed by a component-wise sigmoid function: Sigmoid id (MLP (1, 8, 4))- i... we use filtration functions with shared parameters. Since we can associate persistence tuples with vertices, we concatenate the resulting diagrams to obtain a [V| x (4 * 2) matrix [DP. D2, D9. DdJ, where DP denotes the O-dim diagram obtained using the i-th filtration function. This procedure was also employed by Horn et al. [15]. The obtained diagrams are processed using DeepSet layer with mean aggregator and internal MLP function (V) with 16 hidden and output units, MLP (4 2, 16, 16). We then apply linear layer top of the aggregated features. The overall DeepSet architecture is: MLP (4 2, 16, 16) - Mean Aggregator + Linear (16, 16). Finally, we obtain class predictions using BatchNorm followed by a single-hidden-laye MLP with 16 hidden units: BN (16) - MLP (16, 16, 1).
RePHINE uses the same overall architecture as the PH model. The only differences are that i) RePHINE tuples 3-dimensional (as opposed to 2-dimensional in PH), and RePHINE addi-
hnttpe://chrmmrrs, github..itt.u..... iot.bb..//dttastt/////
htttps:/oob..tanffee
21

---

tionally leverages an edge-level filtration function. Such function follows the architecture of the vertex-level one, i.e. Sigmoid (1, 8, 4)). We note that RePHINE tuples are 3-dimensional instead of 4-dimensional because we removed their uninformative first component (equal to 0) since we only use O-dim diagrams. In other words, we do not leverage missing holes.
Regarding the training, all models follow the same setting: we apply the Adam optimizer [21] for 2000 epochs with an initial learning rate of 10-4 that is decreased by half every 400 epochs. We use batches of sizes 5, 8, 32 for the cubic08, cubic10, and cubic 12 datasets, respectively. All results are averaged over 5 independent runs (different seeds). For all models, we obtain the expressivity metric by computing the uniqueness of graph-leved representations extracted before the final MLP, with a precision of 5 decimals. Importantly, these choices of hyperparameteess ensure that all models have a similar number of learned parameters: 1177 (RePHINE), 1061 (PH), and 1 1129 (GCN).
Real-world data. For computing the standard vertex-color persistence diagrams, we use the code available by Horn et al. [15], which consists of a parallel implementation in PyTorch of the pseudocode in Algorithm 1. Moreover, we apply a multiple filtration scheme and concatenate the O-dim persistence diagrams form matrix representations Then, we apply a DeepSet architecture of the form: MLP (TupleSize * nFiltrations, OutDim, OutDim) + Mean Aggregator Linear (OutDim, OutDim). We use MLPs to define vertex- and edge-level filtration functions. For the 1-dimensional persistence tuples (or missing holes), we first process the tuples from each filtration function using shared DeepSet layer and then apply mean pooling to obtain graph-level representations - this avoids possibly breaking isomorphism invariance by concatenating 1-dimensional diagrams. We sum the 0- and 1-dim embeddings and send the resulting vector to an MLP head. The resulting topological embeddings are concatenated with last-layer GNN embeddings and fed into final MLP classifier.
again similarly to the design in [15].
We carry out grid-search for model selection. More specifically, we consider grid comprised of a combination of 3) GNN layers and {2, 4, 8 filtration funetions. We set the number of hidden units in the DeepSet and GNN layers to 64, and of the filtration functions to 16 i... the vertex/edge-colo filtration functions consist of 2-layer MLP with 16 hidden units. For the largest datasets (ZINC and MOLHIV), we only use two GNN layers. The GNN node embeddings combined using global mean pooling layer. Importantly, for all datasets, we the same architecture for RePHINE and color-based persistence diagrams.
For the TUDatasets, we obtain random 80%//0%//10% (train/val/test) split, which is kept identical across five runs. The ZINC and MOLHIV datasets have public splits. All models are initialized with a learning rate of 10-3 that is halved if the validation loss does not improve over 10 epochs. We apply early stopping with patience equal to 40.
Comparison to PersLay. We followed the guidelines in the official code repository regarding the choice of hyper- parameerrsesssrs.. In particular, PersLay applies fixed filtration functions obtained from heat kernel signatures of the graphs with different parameters, resulting in extended and ordinary diagrams for 0 and I-dimensional topological features. For RePHINE+Linear, we carry out simple model selection procedure using grid-search for the number of filtration functions ((4, 83) and the number of hidden units ((16, 64)) in the DeepSet models.
Hardware. For all experiments, we use Tesla V100 GPU cards and consider a memory budget of 32GB of RAM.
C.3
Computing RePHINE diagrams
Algorithm 2 describes the computation of RePHINE diagrams. The pseudocode has been written for clarity, not efficiency. The replacement for so in real holes depends the choice of edge and vertex filter functions. In all experiments, we employed the logistic function to the output of the feedforward networks (i.e., filtered values lie in [0, 1)) and used to denote the death time of real holes.
D Additional experiments
Here, we complement the experiments synthetic data, providing illustrations of the learned persistence diagrams and reporting results obtained when we combine 0- and I-dimensional diagrams.
In Figure $3, we show the concatenation of the learned persistence diagrams at the end of the training procedure for RePHINE and PH (i.e., standard vertex-color filtration)). In these examples, the RePHINE diagrams are different while the PH ones are identical. We can observe this behavior by
22

---

Algorithm 2 RePHINE
Require: V. E, Values, Values
P Vertices, edges, and edge/vertex-color filter values
uf UNIONFIND( V
persO <- zeros (1,44)
D Initialize the persistence tuples
pers - zeros [),
perso];; 3] t + vValues
>> Pre-set the 'birth' times of each node S do & Pair is equivalent to the zip function in Python for weight E
SINDICES, SVALUES SoRr(eValues)
(u, w) <-
if pers0[[, 4] = 0 then
pers0[e, 4] weight
Save the first filtration step that a node discovered
end if
perso[w, 4] 0 then we 4] < weight
end
younger uf. (()
younger denotes the component that will die
f (f)
if younger older then persl[e. 1] f
A cycle detected
persl[e, 2] weight
persi[e, [3,4]] + 0o
continue
else
if Waluuesyyounger) = vValues[older] then if persO[younger, 4] persO[older, 4] then younger, older, u, < older, younger, w, end if else if Values[younger] VValues[older] then younger, older, t older, younger, end if
Additional disambiguation step
Flip younger, older, and node ids
end if persOlyounger, 2] +- weight
uf.merge((v, w)
Merge two connected components
end for for E uf.roots do
persO[r, 2] + oo
end for R + JOIN pers!) return R
carefully inspecting the multisets of vectors each row of the concatenated tuples (each of the plots in Figure S3). For instance, consider the diagrams in Figure S3(b); in the RePHINE diagram for the top graph, there is with 3 yellow entries which do not appear at the diagram for the bottom graph. However, the representations obtained from Standard PH are identical for these graphs.
In Figure we reported results using only O-dimensional topological features. For completeness, Figure S4 shows learning curves when exploiting both 0 and 1-dimensional diagrams. Overall, we can again observe that RePHINE produces higher expressivity and better fitting capability in comparison to vertex-color persistence diagrams.
23

---

RePLIINE
Standard
RePiLINE
Scandard
RePIINEE
Standand
Cubic08-1
(b) Cubic10-2
(c) Cubic12-3
(d) Cubic10-2
(e) Cubic12-
(f) Cubic12-3
Figure S3: O-dimensional diagrams obtained from RePHINE and PH (standard vertex-color filtrations). These represent pairs of graphs for which the learning procedure in RePHINE could yield different representations, whereas PH produced identical graph-level embeddings.
(+1)
(-1)
Expersiity
Accstees
0.6
RePHINE
0.6
cub11022
cub10-2
cuh-10-2 10-2
1.0
Expesiiity
Aommyy
10000
1500
2000
500
2000
Expressitty
Accuney
0.7
0.5
0.6
Eqocts:
Epocis:
Figure $4: Average learning curves for RePHINE and PH cubic graphs, using both O-dim and 1-dim persistence diagrams. Again, RePHINE can better the graph samples.
24


Reviews:
[{"review_id": "JUmFnUwfBE", "reviewer": "Reviewer_PDW5", "summary": "The paper provides a theoretical analysis of the expressive power of Persistent Homology (PH) features in distinguishing different colored graphs. The paper characterizes the family of graphs that is separable by a 0-dimensional PH using either node filtering or edge filtering and identifies the failure cases. Based on the theoretical analysis, a new PH filtration is proposed that overcomes the previous limitation and is provably strictly more expressive than either node or edge filtering. The new filtering is compared with standard PH filtering on a synthetic dataset and a few graph-classification benchmarks.", "questions": "Going through the Lemmas introduced in the preliminaries and the following section, it is not clear which lemmas/theorems are introduced by the authors and which ones are just reported (if any). \n\nI would add to the comparison soma SOTA method for graph classification.\n\nFor MOLHIV the ROC-AUC is usually reported.", "limitations": "I do not foresee any particular negative societal impact. A discussion on the theoretical and practical (if any) limitations of the proposed method, also w.r.t. SOTA on graph classification, would better help to understand the current and future potential of the method.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The main contribution of the paper lies in the theoretical analysis of the expressive power of PH filtering, which allows one to understand the limits of standard filtering schemes fully and to build a new enriched scheme to overcome them. \nThe paper is generally well-written and drives you through the reasoning that led to the development of the method while introducing all the essential theorems. Fully understanding them and grasping all the implications requires some effort from the reader, and possible to jump forth and backward from the main paper and the supplementary where proofs are given, but this has to be expected in this kind of paper.", "weaknesses": "If the paper is well structured for what concerns the theoretical analysis, the experimental one is a bit lacking. In particular, in its current state, the paper does not position itself with respect to recent methods for graph classification, and it is not clear if it is a practical competitive alternative or if the contribution mostly lies on the theoretical analysis and just paves the road to future possible developments.\n\nA felt also that an analysis of the expressive power bounds of the proposed method could have been interesting. For instance, is there any particular graph structure in which the proposed method cannot distinguish two non-isometric graphs?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful feedback. We address all your questions below. \n\n**W1: \"the paper does not position itself with respect to recent methods for graph classification\"**\n\nThanks for the opportunity to position our work appropriately.  Persistent homology methods that we consider here provide valuable topological information that can often be integrated into recent graph embedding methods such as variants of (geometric) graph neural networks (GNNs) to boost their performance. Therefore, we believe their role is complementary to the existing graph classification methods, so our initial experiments focused on corroborating the benefits of augmenting popular GNNs with topological descriptors. We are currently running experiments to investigate further benefits of integrating the RePHINE diagrams into modern GNNs (e.g., PNA, SpecFormer). We will include these results in the revised version of the manuscript.\n\nBased on the reviews, we have now also compared the proposed method RePHINE with a state-of-the-art persistent homology method Extended PH (Perslay) on several real datasets such as NCI109, Proteins, IMDB-B, and NCI1. Our results demonstrate that RePHINE performs better on these datasets (please see Table 1 in the attached pdf). Thus, beyond the theoretical analyses, the empirical benefits of RePHINE can already be demonstrated.\n\n**W2: \"is there any particular graph structure in which the proposed method cannot distinguish two non-isometric graphs?\"**\n\nThat's another excellent question. Indeed, there are non-isomorphic graphs that cannot be separated based on RePHINE diagrams. In particular, if two graphs have one color, RePHINE cannot separate graphs of equal size with the same number of components and cycles. For instance, a 4-node star graph and a 4-node path graph cannot be separated. We've added a visualization in Figure 1 (in the attached pdf) to show this limitation.\n\n**Q1: \"it is not clear which lemmas/theorems are introduced by the authors and which ones are just reported.\"**\n\nAll Lemmas/Theorems,  including those in the preliminaries and following sections, are introduced and proven in this paper. To emphasize this, we've now added a Table with a summary of our contributions in the Introduction --- we've also included the Table in the attached PDF. Please note that we have now additionally proved that RePHINE is isomorphism invariant (see our reply to reviewer x2he for details).\n\n**Q2: \"I would add to the comparison soma SOTA method for graph classification.\"**\n\nThanks for your comment. As we mentioned in the answer to R1-W1 above, we are running further experiments to substantiate the benefits of integrating RePHINE into SOTA GNNs. We will include these results in the revised version.\n\n**Q3: \"For MOLHIV the ROC-AUC is usually reported.\"**\n\nThanks for catching this. Indeed, the numbers in the paper for MOLHIV are ROC-AUC values. We will make this clear in the revised manuscript.\n\n***\nMany thanks again for your constructive feedback. Based on your review, we will update our paper to include additional results regarding the combination of RePHINE + modern GNNs (SOTA) and clarify our contributions (including their limits). We hope our answers have sufficiently addressed your concerns, and the same translates into your stronger support for this work. "}, {"review_id": "vME4RLPHI4", "reviewer": "Reviewer_x2he", "summary": "The discriminative power of the persistent homology (in certain homological degrees) of vertex- and edge-filtered graphs is characterized in terms of combinatorial structure of the graphs. It is shown that there exist pairs that can be distinguished by the persistent homology of vertex-filtrations but not by the persistent homology of edge-filtrations, and viceversa. This is used to motivate the introduction of a new topological descriptor of graphs which is strictly more discriminative than the persistent homology of both vertex- and edge-filtrations.\nThe performance of this descriptor is evaluated on benchmark datasets.\n\n[Post rebuttal edit] Raised score to 6.", "questions": "## Main questions\n\n6. Your approach seems similar to extended persistence (in the sense of your reference [2]).\nHow does your main strategy (RePHINE) compare to extended persistence and in particular to Perslay (both in theory and in practice)?\nCan you substantiate this with theory or experiments?\n\n7. Is it clear that RePHINE is isomorphism invariant? Since this is an important property for the theorical section of this paper, I believe that this should be addressed explicitly.\n\n8. Is RePHINE stable in the sense of persistent homology? Is this relevant in your setup?\n\n9. In line 58 you mention that you aim to fully characterize graphs that can be distinguished with persistent homology.\nWas this achieved or are there still open questions?\n\n## Minor questions and comments\n\n10. Line 61: Should the subset inclusion be $\\in$?\n\n11. Line 135: the double brace notation has not been introduced and is quite important for this paper.\n\n12. Line 174: I understand that, when you say \"graph\" here, you mean a graph together with a vertex coloring function, as well as a filtration defined on those colors.\nHowever, in line 198 (Theorem 1), the graphs $G$ and $G'$ don't come with a filtration.\nThe convention on what exactly is a graph and what extra structure is used in each result should be made more explicit.\nIf graphs are always assumed to be colored, I would also suggest using the term \"colored graph\", or a term to the same effect.\n\n13. Line 198: In Theorem 1, when you write $D_G$, do you mean diagrams in homological degree 0, in homological degree 1, or both?\n\n14. Line 219: Could you please comment on the relevance of Lemma 7? How can it be used (in theory or in practice)?\n\n15. Line 312: Is there a geometric or topological motivation for \"case a=0\" in line 312?", "limitations": "The paper would benefit from a discussion about limitations of the approach, even if brief. This will help readers asses how useful is their approach for specific tasks, as well as what remains to be done and what are the current promising avenues in the theoretical front.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The theoretical results on the expressiveness of persistent homology of vertex- and edge-filtered graphs are interesting, and they are put to good use in that they motivate the design of a provably stronger topological descriptor of graphs.\n\n2. The fact that the invariant being introduced is strictly more discriminative than the persistent homology of vertex- and edge-filtrations seems to be relevant in practice.", "weaknesses": "3. The exposition is, at times, not that easy to follow. See, in particular, my comment about line 174, below.\n\n4. The experimental section is interesting, but the empirical claims about the performance of the RePHINE would be better substantiated with experimental evaluation on more datasets.\n\n5. The conclusions are a bit too succinct. In particular, the limitations of the approach are not discussed in detail. Relatedly, no future work or open questions are mentioned.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your insightful comments and suggestions to improve the paper. Below we address your concerns.\n\n**W1/Q1: \"the empirical claims about the performance of the RePHINE would be better substantiated with experimental evaluation on more datasets.\" / \"How does your main strategy (RePHINE) compare to ... Perslay\"**\n\nOur initial experiments aimed to 1) corroborate our analysis (synthetic datasets), 2) show that RePHINE also works in scenarios where topological descriptors are combined with GNNs for tackling real-world problems. In total, we considered eight datasets. To further assess the effectiveness of RePHINE, we are currently running experiments regarding integrating RePHINE into SOTA GNNs, including results on additional datasets. We will report these additional experiments in the revised paper.\n\nBased on your feedback, we have now also conducted experiments to compare PersLay and RePHINE on 4 real datasets. To ensure a fair comparison, we processed extended and RePHINE diagrams similarly. In particular, we followed the design of PersLay, i.e., the vectorizations of the diagrams are combined with graph-level features (same as the one used by PersLay) and treated with a linear classifier. We ensured that both methods use identical data samples and used early stopping with the same patience for both methods. The results are in Table 1 of the attached PDF. Overall, RePHINE outperforms PersLay by a significant margin.  \n\n**W2: \"the limitations of the approach are not discussed in detail...no future work or open questions are mentioned.\"**\n\nWhile the complete characterization of the expressivity of RePHINE is an interesting open problem, we can lower-bound its capacity. In particular, if two graphs have one color, RePHINE cannot separate graphs of equal size with the same number of components and cycles. For example, we now show that RePHINE can't separate 4-node star/path graphs (details in the attached PDF).\n\nImportantly, there are many relevant open questions regarding RePHINE/PH in graph learning, including generalization capabilities of existing methods, local versions of RePHINE, and the characterization of which graph properties RePHINE (and other PH-based methods) can compute. Comparing RePHINE and extended PH (or assessing the power of an extended variant of RePHINE) from a theoretical perspective is another interesting open problem. We will add this discussion to the subsection 'Limitations/Future Works' in the revised version of the paper.\n\n**Q2: \"Is it clear that RePHINE is isomorphism invariant?\"**\n\nThank you for raising this question that has led us to formally prove that RePHINE is indeed isomorphism invariant as a new Corollary:\n\n*Let $G$ and $G'$ be isomorphic graphs. Then, any edge-color and vertex-color filtrations produce identical RePHINE diagrams for $G$ and $G'$.*\n\nWe sketch the essential arguments of the proof here. RePHINE diagram’s isomorphism invariance stems from the fact that it is a function of a filtration on a graph, and this filtration is obtained from isomorphism invariant colorings. Further, when matching a vertex with a diagram element (i.e. deciding which vertex 'died' at the death of a component), RePHINE uses minimum and maximum -functions, which are invariant with respect to the order of comparisons done. \n\n**Q3: \"Is RePHINE stable in the sense of persistent homology?\"**\n\nThank you for the interesting question. We believe analyzing the stability properties of RePHINE could be an interesting follow-up work. We will mention this in the newly added subsection ‘Limitations and Future Works’.\n\n**Q4: \"you mention that you aim to fully characterize graphs that can be distinguished with persistent homology. Was this achieved or are there still open questions?\"**\n\nWe analyzed the general case of filtrations based on node and edge colors and indeed provided a complete characterization of attributed graphs that can be distinguished with PH methods that employ these filtrations (using the new notion of color-separating sets). However, there are other types of filtration functions, e.g., based on the spectral decomposition of graph Laplacians, that we have not considered in this paper. Also, there are important open problems, including generalization, stability, and complete characterization of the proposed method, i.e., RePHINE. We believe the novel analyses introduced as part of this work could help in resolving these open problems, and may also foster the rise of other powerful topological descriptors.\n\nBelow, we address the minor issues you pointed out. \n1. **Should the subset inclusion be $\\in$**: Yes.\n2. **the double brace notation has not been introduced**: We introduced the notation for multisets in the revised paper.\n3. **when you say \"graph\" here, you mean a graph together with a vertex coloring function, as well as a filtration defined on those colors ...**: We note that filtration functions do not come with our definition of graphs. We have added the term 'colored (or attributed) graphs' when we define graphs.\n4. **In Theorem 1..do you mean diagrams in homological degree 0, in homological degree 1, or both?** We meant 0-dim diagrams. We have replaced $\\mathcal{D}_G$ with $\\mathcal{D}_G^0$ for clarity.\n5. **Could you please comment on the relevance of Lemma 7? How can it be used (in theory or in practice)?**\nLemmas 6 and 7 motivate the introduction of color-disconnecting sets and help to characterize the expressivity of almost holes. We have added a reference also to Lemma 7 when introducing color-disconnecting sets.\n6. **Is there a geometric or topological motivation for \"case a=0\"?** Case a = 0 corresponds to pairs that are augmented with an independent vertex-color filtration.\n---\nWe hope our answers (including empirical comparison with PersLay, proof of isomorphism invariance, and discussion about open problems and limitations) have sufficiently addressed most of your concerns and that you would kindly consider increasing your score. "}, {"review_id": "zPOga2lvBg", "reviewer": "Reviewer_rXNh", "summary": "The authors introduce RePHINE, which calculates 0-dimensional persistent homology (PH) with respect to the filtration on edge colors, augmented with so-called missing holes and vertex color information. They establish the necessary and sufficient conditions for distinguishing graphs. RePHINE is shown to be more expressive than both standard 0-dim and 1-dim PH, can be easily integrated into GNNs, and is demonstrated to boost their expressive power on several benchmarks for graph classification.", "questions": "Main questions are formulated in the weaknesses (W1)-(W6) above.\n\n(Q1) Abstract: “… provably more powerful than both”. The word both is confusing here, is your method more powerful than the two combined, or more powerful than each of them separately?\n\n(Q2) What is a suitable metric for the augmented persistence diagrams? A brief comment is sufficient, and can be placed in future research.\n\n(Q3) Which software do you use for calculation of PH?\n\nSome minor suggestions:\n\n-\t“Experiments support our theoretical analysis and show the effectiveness of RePHINE on five real-world datasets.” -> “Experiments support our theoretical analysis and show the effectiveness of RePHINE on three synthetic and five real-world datasets.”\n-\tProvide a reference for persistence diagram (e.g., in Section 2), so that readers can find more information, and to make it clear that this is not defined for the first time here in your work.\n-\tExplicitly mention that all lemmas and theorems are proved in Appendix B, since one might wonder if some or all of these are earlier results.\n-\tLemma 1 Vertex-based filtrations … -> Lemma 1 Injective vertex-based filtrations …\n-\tFor better readability, it would be good to also have explicit Definitions for separating and disconnecting set. Improve consistency in naming theoretical results, e.g., if Lemma 6 (Edge-based almost holes as disconnecting sets), then it is better that Lemma 4 (Vertex-based almost holes as color-separating sets).\n\n-\tA visual or table summary (can be placed in Appendix B) of your theoretical results could really help the readability of Section 3 and the impact of your work. For example, some of the table rows could be the following:\n1) Real holes (d = infty) of 0-dim PH wrt vertex-color filtration --- Component-wise colors --- Lemma 2\n2) Almost holes (b neq d, d < infty) of 0-dim PH wrt vertex-color filtration --- Color-separating sets --- Lemma 3\n3) Birth time of 0-dim persistence interval wrt vertex-color filtration --- Vertex color --- Lemma 5\n4) Almost holes  (b neq d, d < infty) of 0-dim PH wrt edge-color filtration ---- Disconnecting sets --- Lemma 6\n\n-\tWhat is {{ on line 135, line 160, line 182, line 199, …?\n-\tIn Section 3, you denote birth and death values with b and d (I think this is more common and readable), but you use a and b in Section 4.\n-\tIntroduce the augmented PH as an explicit Definition in Section 4, as this is your main contribution.\n-\tCite specific Appendix (e.g. Appendix B), rather than pointing to the general Appendix.\n-\tCapitalization in References: PersLay, Kolmogorov, Rayleigh-Bénard, Leman\n", "limitations": "Limitations and future work are not discussed.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "(S1) The three questions in the Introduction nicely position and motivate the work, and the presentation of the main contributions is very clear.\n\n(S2) The theoretical results are relevant, as they discuss in detail the expressivity of PH on vertex-color and edge-color filtrations, and expressivity of RePHINE. I do not have a good overview of PH on graphs, so I cannot comment on the novelty of results, and I did not check the supplementary material for proofs.\n\n(S3) Experiments are carried out on 3 synthetic and 5 real-world datasets.\n", "weaknesses": "(W1) The related work seems not be detailed enough and is hard to identify.\n\n(W2) The name RePHINE is clever and nice. However, the word interleaving suggests interleaving distance (esp. relevant in TDA), so it would probably be better to replace this with e.g. interplay or integration. Also, it is somewhat a misnomer since you are not really using a filtration on nodes (this information does not influence birth and death values), so it might be better to rephrase that part too (e.g. Refined PH by incorporating node-color on edge-based filtration)?\n\n(W3) From the beginning of the paper, I was confused what the particular interplay between vertex- and edge-based PH will be. This was most pronounced in Section 3.3, since your way of edge-coloring definition, if used together with vertex-coloring, does not satisfy the definition of simplicial complex. For example, f(orange)=1, f(blue-orange)=2, f(blue)=3, so that an edge can appear in the filtration before the two incident vertices appear. Stressing earlier on (already in Section 1) that you calculate PH on edge-based filtration, including so-called missing holes and augmenting it with vertex-color information would be helpful. See related comment (W2) on the acronym RePHINE above. \n\n(W4) You write: “We note that missing holes correspond to cycles obtained from 1-dim persistence diagrams.” How does you approach compare to concatenated standard 0- and 1-dim PH on edge-based filtration?\n\n(W5) Experimental results on synthetic data: More information about the data should be included (in Appendix C.1). What exactly is the problem/goal here? What type of graphs results in the same RePHINE representation (in particular for cub12-3)? You write that you compare with 0- and 1-dim PH on vertex-color filtration, but what exactly do you mean by this, is this information concatenated (union of sets is considered)? What about PH on edge-color filtration? Why are standard PH and GNNs performing so poorly?\n\n(W6) Experimental results on real-world data: You write that you compare against standard color-based PH, but what do you mean with this? See related comments in (W4). It would be interesting to look at the results in more detail, in particular to discuss some examples that would be wrongly classified with other approaches, but that are successfully tackled with your method, but also at the examples that cannot be classified properly with your approach (the discussion may be placed in an appendix).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and thoughtful review. You have raised very pertinent points. Below, we address your questions/comments.\n\n**W1: \"The related work seems not be detailed enough and is hard to identify.\"**\n\nThanks for your comment. In the Introduction, we decided to group references together for conciseness. To alleviate the issue you raised, we will provide a more detailed overview of related works in the supplementary material (in a new section Related Works).\n\n**W2: \"The name RePHINE is clever and nice. However, the word interleaving suggests interleaving distance (esp. relevant in TDA), so it would probably be better to replace this with e.g. interplay or integration.\"**\n\nThanks very much for the excellent suggestion. We agree that 'Refined PH by incorporating node-color into edge-based filtration' is apt for the proposed method, so have accordingly decided to adopt this rephrasing. \n\n**W3: \"Stressing earlier on (already in Section 1) that you calculate PH on edge-based filtration, including so-called missing holes and augmenting it with vertex-color information would be helpful.\"**\nWe have reworded descriptions in the Abstract, Introduction, and Section 4 to better reflect how RePHINE works. For instance, the Abstract now reads: \"RePHINE efficiently incorporates vertex-color information into edge-level filtrations, achieving a scheme ...\".\n\n**W4: \"How does you approach compare to concatenated standard 0- and 1-dim PH on edge-based filtration?\"**\n\nWe note that RePHINE is more expressive than the union of the multisets of 0- and 1-dim PH on edge-based filtration. In particular, the two graphs in Figure 4(c) of the paper cannot be distinguished by either 0-dim or 1-dim PH. However, we can obtain two different RePHINE diagrams for such a graph as we show in part (3) of the proof of Theorem 4.\n\n**W5: Regarding details and further analysis of the results on synthetic data.**\n\nThe cubic datasets comprise non-isomorphic 3-regular graphs. From these graphs, we create a classification problem by assigning each graph a binary class. Given the partition, we assess if the existing methods can overfit (correctly classify all) the samples. When we compare RePHINE with 0- and 1-dim PH on vertex-color filtration, we mean the union of the 0- and 1-dim diagrams.  \n\nRegarding the analysis, we have only compared RePHINE to vertex-color filtration as it has been used in the reference work (TOGL). Nonetheless, in the revised version of the paper, we will also include results for diagrams obtained from edge-level filtrations. To understand why PH works poorly, we report diagrams (after learning) for two instances of cubic-10-2 in the attached PDF. We noticed that the original code of TOGL for vertex-color filtrations uses $max(f(c))$ instead of infty, which makes it not distinguish almost and real holes in some instances. We will also provide a similar discussion on the reasons for the failure of GCNs and report obtained diagrams for other graphs (and synthetic datasets) in the supplementary material.\n\n**W6: \"Experimental results on real-world data: You write that you compare against standard color-based PH, but what do you mean with this?\"**\n\nBy standard color-based PH, we mean 0-dim and 1-dim persistence diagrams obtained from vertex-color filtrations. To the best of our knowledge, edge-color filtrations have not been used in graph learning. We will clarify this in the revised manuscript.\n\n**Q1: \"Is your method more powerful than the two combined, or more powerful than each of them separately?\"**\n\nRePHINE is more expressive than the union of the families of node- and edge-color filtrations. In particular, in Theorem 4, saying that RePHINE is strictly more expressive than vertex- *or* edge-level filtration implies that it is more powerful than they combined (union only allows the separation of graphs that can be separated by one of the filtration types).\n\n**Q2: \"What is a suitable metric for the augmented persistence diagrams?\"**\n\nThis is an interesting question. In particular, future research could consider the suitability of the bottleneck distance for RePHINE diagrams with necessary changes. \n\n**Q3: \"Which software do you use for calculation of PH?\"**\n\nOur code is based on the official repo of Topological GNNs. As such, we have modified their routine to compute our augmented diagrams. It consists of a Torch implementation using a Find-Union data structure.\n\nIn the following, we list the minor suggestions. For conciseness, we mark with $\\checkmark$ the accepted suggestions. \n1. $\\checkmark$ “Experiments ... five real-world datasets.” $\\rightarrow$ “Experiments ... on three synthetic and five real-world datasets.”\n2. $\\checkmark$ Provide a reference for persistence diagram (e.g., in Section 2)\n3. $\\checkmark$ Explicitly mention that all lemmas and theorems are proved in Appendix B.\n4. $\\checkmark$ Lemma 1 Vertex-based filtrations … $\\rightarrow$ Lemma 1 Injective vertex-based filtrations …\n5. It would be good to also have explicit Definitions for separating and disconnecting set. --- **This might be adopted if the page limit allows.**\n6. $\\checkmark$ Improve consistency in naming theoretical results.\n7. $\\checkmark$ A visual or table summary (can be placed in Appendix B) of your theoretical results could really help the readability of Section 3 and the impact of your work.} **See attached PDF.**\n8. $\\checkmark$ \\textbf{What is $\\{\\{$ on line 135, line 160, line 182, line 199?} **We use $\\{\\{$ to represent multisets.**\n9. $\\checkmark$ In Section 3, you denote birth and death values with b and d, but you use a and b in Section 4.} **We are now using $b$ and $d$, as suggested.**\n10. $\\checkmark$ Introduce the augmented PH as an explicit Definition in  Section 4.\n11. $\\checkmark$ Cite specific Appendix (e.g. Appendix B).\n12. $\\checkmark$ Capitalization in References\n\n---\n We're grateful for your thoughtful and perceptive comments, and hope our answers have improved your assessment of this work.\n"}, {"review_id": "QTqaCdHZ68", "reviewer": "Reviewer_oULm", "summary": "In this paper, the authors discuss the limitations of message-passing graph neural networks (MP-GNNs) in terms of the Weisfeiler-Leman test for isomorphism. They explore the use of persistent homology (PH) to augment graph models with topological features but highlight the challenge of identifying the class of attributed graphs that PH can recognize. To address this problem, they introduce the concept of color-separating sets. They establish necessary and sufficient conditions for distinguishing graphs based on the persistence of their connected components using filter functions on vertex and edge colors. Based on these insights, they propose RePHINE, a method for learning topological features on graphs. RePHINE integrates both vertex-level and edge-level PH, claimed to be more powerful than either category alone. When incorporated into MP-GNNs, RePHINE enhances their expressive power.", "questions": "Please refer to the sections above.", "limitations": "Please refer to the sections above.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper presents new theoretical results and introduces a concept of color-separating sets, providing a resolution to the problem of recognizing attributed graphs based on the persistence of their connected components. The authors establish necessary and sufficient conditions for distinguishing graphs using filter functions on vertex and edge colors. They also propose RePHINE, a method for learning topological features on graphs, which integrates both vertex-level and edge-level persistent homology.", "weaknesses": "While the theoretical contributions of this paper are new, there is room for further exploration and validation in real-world experiments. The current evaluation primarily focuses on controlled simulated datasets, limiting our understanding of RePHINE's performance in practical scenarios. It is equally important to conduct more comprehensive experiments using real-world data to fully assess the efficacy and applicability of the proposed approach. Addressing these limitations would strengthen the practical relevance of the paper's findings. Are there any specific limitations or challenges when applying RePHINE to real-world applications? Additionally, it would be interesting to understand the factors that contribute to the marginal performance gain of RePHINE on most real-world datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback. We reply to your comments/questions below.\n\n**\"There is room for further exploration and validation in real-world experiments. The current evaluation primarily focuses on controlled simulated datasets, limiting our understanding of RePHINE's performance in practical scenarios.\"**\n\nWhile we agree that there is room for improvements, we would like to highlight that our initials experiments were mainly designed to 1) validate our theoretical findings (synthetic datasets), and 2) show that the proposed diagrams can be easily integrated into GNNs to boost their predictive performance on popular benchmarks on graph classification. Thanks to your comment, we are currently running experiments to investigate further benefits of integrating the RePHINE diagrams into modern GNNs (e.g., PNA, SpecFormer). We will include these results in the revised version of the manuscript.\n\nImportantly, we have now compared RePHINE diagrams with Extended Persistence diagrams used in the PersLay model. Our results demonstrate that RePHINE outperforms PersLay on four real-world datasets by a large margin (please see Table 1 in the attached pdf). Thus, we believe that beyond the theoretical analyses, the empirical benefits of RePHINE can already be demonstrated.\n\n**Are there any specific limitations or challenges when applying RePHINE to real-world applications?**\n\nWe believe that topological descriptors (such as RePHINE) work complementary to existing graph classifiers rather than standalone methods. As a standalone method, we know RePHINE has theoretical limitations. In particular, for unattributed graphs, RePHINE cannot separate graphs of equal size with the same number of components and cycles (please see the example in the attached PDF). \n\nHowever, given RePHINE's improved expressivity at the same computational cost as vanilla vertex-color filtrations, RePHINE has the potential to become the default choice for topologically enriched graph models in real-world applications. \n\n**It would be interesting to understand the factors that contribute to the marginal performance gain of RePHINE on most real-world datasets.**\n\nWhile it is hard to provide a definitive explanation for subtle performance differences, we believe that the minor gains come from our specific architectural choices, which isolate persistence diagrams while keeping other components unchanged. We note that in the comparison against the PersLay model, we can observe a significant difference in performance.\n"}, {"review_id": "PScH4Vg9ab", "reviewer": "Reviewer_BFX1", "summary": "- The paper presents a comprehensive analysis of two types of color filtrations on graphs, focusing on their expressiveness. \n\n- The paper introduces a novel topological summary RePHINE that combines both node and edge persistence diagrams. The proposed summary is proven to be more expressive than either node or edge persistence diagrams alone.\n\n- The authors conduct experiments on synthetic and real-world datasets. They leverage a combination of RePHINE and a GNN structure to evaluate its performance. ", "questions": "- line 47-52: I think there is some syntax issue with the appearance of [Theory], [Methodology] and [Experiments]\n- line 142: \"disconnect\" should be \"disconnects\".\n- line 172: please mention that Q is a color separating set in this sentence.\n- line 502: what does \"disjoint union\" here mean? What does \"these sets\" refer to? could you please provide an explicit description of the set you are constructing here?\n- line 510: I don't think $\\{\\{X_i\\}\\}$ should have $l$ as a superscript. Are you also referring to connected components with $l$ colors instead of subgraphs?\n- line 513: \"l+1 the\" -> \"l+1 th\"\n- line 693: \"it is not injective\" should be \"is not injective\".", "limitations": "The limitations of the method are not adequately discussed. I think it would be beneficial for the authors to discuss applicability of the proposed method to handle large scale graphs.\n\nThere are no potential negative societal impact of the work.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The presented method RePHINE for mixing 0- and 1- dim information is interesting and, as far as I know, is novel. \n- A remarkable strength of the proposed method is its theoretical expressiveness, which surpasses the capabilities of utilizing 0- or 1-dimensional information in isolation.\n- The paper is well presented and effectively communicates its ideas, ensuring a high level of clarity and ease of understanding for readers.", "weaknesses": "One weakness of the paper lies in the experimental evaluation section, which could benefit from a more comprehensive comparison with existing methods, such as the method proposed in [28]. Specifically, the paper could have included a comparative analysis between the proposed method and the local Persistent Homology (PH) method based on subgraph persistence diagrams included in  [28].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive feedback. In the following, we address all your questions. \n\n**W1: \"One weakness of the paper lies in the experimental evaluation section, which could benefit from a more comprehensive comparison with existing methods, such as the method proposed in [28].\"**\n\nWe note that our initial experiments mainly focused on corroborating our theoretical analysis (synthetic datasets) and on assessing the benefits of combining RePHINE diagrams with popular GNNs for improved predictive performance. However, thanks to your comment, we have also compared RePHINE with a method that leverages extended persistence diagrams: PersLay. Our new results (please see Table 1 of the attached PDF) demonstrate that RePHINE outperforms PersLay on popular graph classification benchmarks.\n\nWe have opted for PersLay instead of [28] due to the similarity between the evaluation setups and the ease of adaptation --- [28] mainly considers node classification tasks. Moreover, we are currently running experiments to investigate further benefits of integrating the RePHINE diagrams into modern GNNs (e.g., PNA, SpecFormer). We will include these results in the revised version of the manuscript.\n\n**Q1: \"I think there is some syntax issue with the appearance of [Theory], [Methodology] and [Experiments]\"**\n\nThanks for pointing this out. We will make sure that there will be no such syntax issues in the revised manuscript.\n\n**Q2: \"disconnect\" should be \"disconnects\"**.\n\nYes, thanks for the careful reading.\n\n**Q3: please mention that Q is a color separating set in this sentence.**\n\nWe have modified that in the revised paper. Now the sentence reads: \n\n*We note that when $G$ and $G'$ have identical component-wise colors, the sets $\\\\{w \\in V | c(w) \\in Q\\\\}$ and $\\\\{w \\in V' | c'(w) \\in Q\\\\}$ induced by the color-separating set $Q$ are separating sets for $G$ and $G'$, respectively.*\n\n**Q4: \"what does \"disjoint union\" here mean? What does \"these sets\" refer to? could you please provide an explicit description of the set you are constructing here?\"**\n\nWe agree that the construction was not clear. Thanks for pointing this out.  We meant that when $G$ and $G'$ have distinct component-wise colors, there must be some connected component $C_h$ in $G$ such that $\\\\{X_h\\\\} \\neq \\\\{X'_j\\\\} $ for $ \\forall 1 \\leq j \\leq k $. \n\nThen, if assumed $\\beta^0_G = \\beta^0_{G'}$, the unmatched component-colors come in pairs i.e. $G$ must have as many unmatched component-color sets as $G'$.  The collection of sets of unmatched component-color pairs is considered in the proof.\n\nWe have clarified the language throughout the proof, and rewritten the mentioned part as follows :\n\n*When $G$ and $G'$ have distinct component-wise colors [math was ommited here due to markdown issues], there must be at least one connected component $C_h$ in $G$ such that $\\\\{X_h\\\\} \\neq \\\\{X'_j\\\\} $ for $ \\forall 1 \\leq j \\leq k $. Let us now call such $\\\\{X_h\\\\}$ a set of unmatched component colors*. \n\n**Q5: \"I don't think $X_i$ should have $l$ as a superscript. Are you also referring to connected components with $l$\n colors instead of subgraphs?\"**\n\nThis is a typo, the superscript should be $k$. We fixed it.\n\n**Q6: line 513: \"l+1 the\" -> \"l+1 th\"**. \n\nWe have fixed that typo in the revised paper.\n\n**Q7: \"it is not injective\" should be \"is not injective\".**\n\nYes, thanks for the careful reading.\n\n---\nWe hope our answers have addressed the points you have raised, and improved your view of the manuscript.\n\n"}]

Author rebuttal:
We are grateful to all the reviewers for their time and insightful comments, as well as to the (senior) area, program, and general chairs for their service to the community.

We are glad to note the positive response of all the reviewers, and specifically, their acknowledgments that our work is **interesting and novel** (x2he, BFX1) and **provides a resolution to the problem of recognizing attributed graphs** based on the persistence of their connected components (oULm). Also, reviewers found that our work can **allow one to understand the limits of standard filtering schemes** and **build new enriched schemes to overcome them** (PDW5). Finally, our **theoretical contributions are said to be well presented and clear** (rXNh, BFX1, PDW5), **relevant in practice** (rXNh, x2he), and **supported by experiments on eight datasets** (rXNh).

To the best of our efforts, we’ve tried to address all the specific comments, including the minor ones, that have been raised by each reviewer. In particular, some of the main revisions are:

- Additional experimental results on the comparison between RePHINE and Extended Persistence Diagrams (PersLay);
- Proof that RePHINE is isomorphism invariant (newly added Corollary 1);
- New subsection about 'Limitations and Future Works';
- Clarifications regarding the main contributions (newly added Table with an overview of our theoretical results), and exposition of RePHINE diagrams (now as a formal definition);
- Added visualizations about the graphs and diagrams obtained from the synthetic experiments.

Moreover, we are currently running experiments to show additional results on 1) the combination of RePHINE with SOTA GNNs; 2) more (larger) datasets.

We believe that acting on reviewers’ feedback has reinforced the many strengths of this work, and we thank them again for their very constructive comments.

Meta-review: This paper and the ensuing discussion was a joy to read and behold. It presents a direly-needed investigation into the theoretical limits of persistent homology in graph learning, while developing new ways to leverage topological information in neural networks. The paper is technically sound and well-written—a fact that was acknowledged by all reviewers—and I fully agree with the reviewers here. It is thus my pleasure to **endorse this paper for presentation at NeurIPS**.

Moving forward, the authors are encouraged to further improve the text by positioning and contextualising their work, with a particular eye towards theoretical or empirical limitations of their work.
Decision: Accept (oral)