On topological descriptors for graph products
Authors: Mattie Ji
Amauri H Souza
Vikas K Garg
Venue: NeurIPS 2025 poster ()
Keywords: topological data analysis
graph neural networks
graph machine learning
Primary area: theory
TL;DR: We study and give algorithms to compute topological descriptors of color-based filtrations on the Cartesian product of graphs.

Abstract: Topological descriptors have been increasingly utilized for capturing multiscale structural information in relational data. In this work, we consider various filtrations on the (box) product of graphs and the effect on their outputs on the topological descriptors - the Euler characteristic (EC) and persistent homology (PH). In particular, we establish a complete characterization of the expressive power of EC on general color-based filtrations. We also show that the PH descriptors of (virtual) graph products contain strictly more information than the computation on individual graphs, whereas EC does not. Additionally, we provide algorithms to compute the PH diagrams of the product of vertex- and edge-level filtrations on the graph product. We also substantiate our theoretical analysis with empirical investigations on runtime analysis, expressivity, and graph classification performance. Overall, this work paves way for powerful graph persistent descriptors via product filtrations. Code is available at https://github.com/Aalto-QuML/tda_graph_product.

On topological descriptors for graph products
Mattie Ji University of Pennsylvania mji13@sas. upenn edu
Amauri H. Souza Federal Institute of Ceará
Vikas Garg Aalto University Yai Ltd vgargocsail.nm
edu.br br
Abstract
Topological descriptors have been increasingly utilized for capturing multiscale structural information in relational data. In this work, we consider various filtrations the (box) product of graphs and the effect their outputs the topological de- scriptors the Euler characteristic (EC) and persistent homology (PH). In particular, we establish a complete characterization of the expressive power of EC on general color-based filtrations. We also show that the PH descriptors of (virtual) graph prod- ucts contain strictly more information than the computation on individual graphs whereas EC does not. Additionally, we provide algorithms to compute the PH dia- grams of the product of vertex- and edge-level filtrations on the graph product. We also substantiate our theoretical analysis with empirical investigations on runtime analysis, expressivity. and graph classification performance. Overall, this work paves way for powerful graph persistent descriptors via product filtrations. Code is available https: // thub. com/ Aalto- tttttaaapa_prrduuuuue
Introduction
Message-passing GNNs are prominent models for graph representation learning [19]. However, they are bounded in expressivity by the WL. hierarchy [33-35, 50) and cannot compute fundamental graph properties such as cycles connected components [10, 18]. Topological descriptors (TDs) such as those based on persistent homology (PH) and the Euler characteristics (EC) can provide such information and thus being increasingly employed to augment GNNs, boosting their empirical performance [7-9, 24, 48, 51].
In this work, study two prominent types of topological descriptors based on PH [1. 13] and EC [40, 42, 46] respectively. Both descriptors are defined with respect to fixed filtration of a graph. On high level, PH keeps track of the birth and death times of topological features (e.g., connected components and loops) in (parameterized) graph filtration. EC a simpler, less expensive invariant that keeps track of the number of vertices minus the number of edges in the filtration. Both PH and EC have found use across a wide range of applications in GNNs [16, 36, 42].
A precise characterization of PH has been established for graphs based [26]. Here, we offer a complete characterization the expressivity of EC in terms combinatorial data the colors of the graph. EC also compares favorably with other TDs in terms of computation, which is another important aspect we explore here. In particular, we streamline PH and EC with what call their "max" versions. We show that the vertex death times, well the cycle birth times, of vertex-level and edge-level max PH are the same. We also establish that max EC retains the expressivity of EC, but is more-cost effective than EC. Interestingly, expressivity equivalence on graphs extends to a more general equivalence for color filtrations on finite higher-dimensional simplicial complexes. This immediately opens avenues for integrating max EC as an economical alternative to PH-based TDs into Topological Neural Networks, which generalize GNNs through higher-order possagg-passing [5, 6, 15, 37, 38] and have recently been shown to benefit from TDs both theoretically and empirically [47].
color-based filtrations in
show that this
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Overview of our theoretical results.
Expressive Power of PH and EC (Section 2, Matching Vertex Deaths and Cycle Births within max PH EC Diagram max EC Diagram on graphs
Proposition
Theorem 1
The Combinatorial Characterization of EC Diagrams on Graphs
Theorem 2
Generalization EC = max EC to Simplicial Complexes
Theorem 3
Topological Descriptors on Graph Products (Section 4):
EC of Product Graphs Does Not Add New Information PH of (Virtual) Product Graphs > PH of Components
Proposition
Corollary
Computational Methods for Products Filtrations (Section 5); Product of Vertex Filtrations = Some Vertex Coloring on Product Product of Edge Filtrations Some Edge Coloring on Product Algorithm for 0-th Persistence Pairs for Vertex Product Filtrations Theorem 4
Proposition 6 Proposition
Algorithm for 0-th Persistence Pairs for Edge Product Filtrations
Theorem 5
Algorithm for 1-st Persistence Pairs for Product Filtrations
Proposition
From practical micro-level perspective, the design of effective filtration functions is also paramount. However, almost invariably. filtration functions are either fixed a priori or learned without any structural considerations (e.g., symmetries), obfuscating how they about the corresponding diagrams. We seek to address this gap from a rigorous theoretical perspective, in pursuit of principled design of richer topological descriptors.
The (box) product graphs [27] naturally leads to symmetries and thus provides an effective starting point for us, where treat individual components graph fractals. From machine learning perspective, graph products also arise naturally in the context of subgraph GNNs [3, 4], serve as natural tool for modeling and analyzing multi-way data [29, 45] and relational databases (see, e.g..
Motivation in Section 4), and have been incorporated in various GNN architectures [14, 43).
For two colored graphs G and H, there is natural coloring the graph product GOH. This enables us to consider vertex- and edge-level color-based filtration on GDH. Under technical modification the graph product, show that the PH of the graph product is strictly more expressive than the PH of the individual components. Surprisingly, the benefits of graph products under PH do not extend to EC. Leveraging that taking the EC of graph products provides does not provide any expressivity benefit beyond the EC of individual components.
complete characterization of the expressive power of EC, we show
notable subcollection of filtrations on graph products given by the (box) product of filtrations on the individual components. We initiate here a formal analysis by characterizing product filtrations: we establish that the product vertex filtrations the max of vertex colors, and that the product of edge filtrations is certain edge coloring on the product. We also provide algorithms to track the evolution of persistence diagrams under the product filtration induced by vertex filtrations and edge filtrations respectively (in fact, the algorithm for I-dimensional features works for any product filtrations). This gives a computationally cost-effective method to compute these PH diagrams.
In sum, our work introduces a calculus for topological descriptors under the graph product. We summarize our theoretical results in Table and relegate all the proofs to the Appendix.
Preliminaries
A graph is the data G = (V, E, X) where V is finite vertex set, E ECV V x V is the set of edges, e: X is vertex coloring function, and X the finite set of possible colors. An isomorphism between graphs G = (V, E, X) and G' (V', E' c' X") is bijection h: - V' such that (a) c' a and (b) (v, w) E and only (h(w), h((r)) E F'. We will only consider finite simple graphs in this work, and all graphs in this work will share the same coloring set.

---

In this work, we consider two types of color-based filtrations based on vertex vertex-level and edge-level. Definition 1 (Color-Based Filtrations). On color set X, we consider the pair of functions (fv : X + I. fe: X x X + Bso) where fe is symmetric (ie, felc,d') = fe(c',)) c)). On a graph G with a vertex color set X, (fer induces the following pair of functions (Fu SUVEEE Fe;
R2o).
1. For all v E V(G). F.(u) = fulc(u). For all e E E(G) with vertices v1. V2. Fule)= (ax(Fo(V1)) F.()) Intuitively, we are assigning the edge e with the color o(arg max,, Fu(U)) (the vertex color that has a higher value under fu).
2. For all
V(G), Fe(v) O. For all e E e{G) with vertices v1, U2 Fele) = fe(c(11),d()) Intuitively, we are assigning the edge e with the color (c(v1),((22))
For each I E RR we write Gf == ((-((_ 1) and Gt- == F ((- (). When there is a clear fixed choice of filtration, we may drop the superscripts and simply write G+.
Note we used Gf as opposed to Gf- to emphasize that the function G + (IG) hER, (G( )R) is well-defined for any graph G with the coloring set X. The lists (G.")eEs JIE and (G- JIER define vertex filtration of by F, and an edge filtration of G by Fg respectively. is clear that G. can only change when / crosses a critical value in (c((c) e E X), and G can only change when t crosses critical value in [,f((e, c2) : (ci, 62) E X x X3. Hence, we can reduce both filtrations to finite filtrations at those critical values.
We now review the two relevant classes of topological descriptors (TDs) for us, namely, persistent homology (PH) and the Euler characteristic (EC).
2.1 Persistent Homology
A vertex v (ie. O-dimensional persistence information) is born when it appears in given filtration of the graph. When we merge two connected components represented by two vertices and w, we use decision rule to kill off one of the vertices and mark the remaining vertex to represent the new connected component. A cycle (ie. 1-dimensional persistence information) is born when it appears in a given filtration of diagram, and it will never dic. For color-based vertex and edge filtration, there a canonical way to calculate the persistence pairs of graph with a given filtration. We refer the reader to Appendix A of Immonen et al. [26] for a precise introduction. We say a O-th dimensional persistence pair (b, d) is a real hole if oo, an almost hole if b * d < oc, and a trivial hole if b = d. We say that a birth or death of a vertex is trivial if its persistence tuple is trivial hole.
Definition Let f = (fr. fe) be on the coloring set X. The persistent homology diagram of graph G is collection PH(G, f) composed of two lists PH( (
where PH(G, f)y are all the persistent pairs in the vertex filtration (Gf- heR and PH(G, f) are all the persistent pairs in the edge filtration JEER htER.
PH is an isomorphism invariant (Theorem 2 of Ballester and Rieck (2]) that generalizes an older invariant- the homology. We will sometimes use (G) and 31 (G) to denote the 0-th and 1-st Betti number of a graph (ic. the rank of the O-th and 1-st homology).
2.2 Euler Characteristic
Including topological features in graph representation learning using persistent homology can be computationally expensive. The Euler characteristic (EC) provides a weaker isomorphism invariant that is casier to compute (but typically less expressive). For graph G, the Euler characteristic X(G) is given by X(G) = #V( # #EG).. Given a filtration of graph G, we can track its Euler characteristic throughout the filtration.
Definition 3. Let = (Jor be on the coloring set X. Write an <.. < On as the list of values Je can produce, and bj < < bm as the list of values fe can produce. The EC diagram of a graph G two lists EC(G. EC(G, f) is the list (x(G())
EC(G, LEC(G, where EC(G. f) is the list (x(G), Va and
We would also like to consider weaker variant of EC that we will call the max EC. Definition 4. Given only a vertex coloring function fo : X - By We define the max EC diagram of G as EC (G, fo) == EC(G, (fu, h(ff))), where h(fo) X x X + Rso is defined
3

---

as h(ff)) = max(fe(c), fc(2)) Note that max EC is the restriction of EC to only the max-induced edge filtrations.
The reader might wonder what happens when could consider a suitable analog of max PH as well. We discuss this possibility in Appendix B and give an explicit method to compute it.
Proposition 1. Write f (J > O, I(Jo)), where h defined Definition 4. The vertex death times (as multi-set) of PH, f) and PH(G, 8) are the same. The cycle birth times are also the same.
3 The Expressive Power of the Euler Characteristies
In this section, we will discuss surprising equivalence between the expressivity of max EC diagrams and EC diagrams on graphs.
Theorem 1. EC and EC"" have the same expressive power, that is, EC can differentiate non-isomorphic graphs and H if and only if F.C" can also differentiate them.
In fact, Theorem I will follow as an immediate corollary of a stronger theorem that will prove below, where we give complete characterization of the expressivity of (max) EC diagrams on graphs. We will first diseuss two complete characterizations of the expressivity of EC with respect to vertex-level and edge-level filtrations.
Let G, H be two graphs both vertices. We will consider the following combinatorial objects.
Notation:
We use (a b) to denote the set of edges in with endpoints being a vertex of color and a vertex of color b. Va(a) to denote the set of vertices in G with color and G(c), (c) to denote the subgraphs of G, generated by the vertices of color c.
In our next results, Proposition 2 and Proposition 3, we establish that the (max) EC diagrams of graph G may be completely interpreted in terms of the combinatorial data provided by the objects Ea(a, b), Va(a) and G(c) defined in the notations above.
Proposition 2 (Characterization of (max) EC Edge Filtrations). The following are equivalent:
X x X - R, ECIG, g) EC(H, R EC EG, 3. # Fa(a, b) #Fu (a, b) for all colors a, b E X.
1. For all (symmetric) edge color functions
2. For all vertex color functions f +
EC" (H,
Proposition 3 (Characterization of (max) EC Vertex Filtrations).
The following are equivalent:
1. For all vertex color functions f X - R. ECIG, n) = FC(HH, f)y
2. For all vertex color functions f: f X + R, EC (G. f) = FC (H, f) # Eu Eu b).
3. For all a + b,c X, X(G(c)) (HH()) (c)) and # Ea
Combining the statements of Proposition 2 and Proposition 3, we obtain the following theorem.
Theorem (Characterization of (max) EC Diagrams). The following are equivalent:
1. G and H have the same EC diagram for any choice of coloring functions.
2. G and have the same max EC diagram for any choice of coloring functions.
3. #Vc(c) = # Vn (c) for all e E X and # Ec(a, b) E (a, b) for any a, b E X.
While the majority of our work is focused on graphs, the equivalence of EC and max EC is a special case of a more general equivalence on the level of (colored) simplicial complexes (see Appendix D).
Theorem 3. There is natural extension of the definition of EC and max EC to colored simplicial complexes such that they have the same expressive power for color-based filtrations.
4 Persistent Topological Descriptor for Graph Products
When dealing with large or complex graphs that have the structural property being some product, it is often easier to work with the components of the graph product rather than the graph as whole.

---

There are common situations where graph data have natural product structure (e.g. relational databases [41]. Hamming graphs [23, 25]) that can be analyzed using the methods here.
Our focus is to look at topological descriptors on product of graphs, as a special kind of structure.
Definition 5. Let G, H be graphs, the box product (Cartesian product) of G and H is the graph GOH, where the vertex set of GDH is the set {[g, h) E ( E V(H)) and the edge set constructed as follows. For vertices (g); h1) and (g2, h2), we draw an edge (f) 91 92 and by ~ l22 in H or (2) h1 = h2 and 91 ~ in G. Here, by hy ~ h2, we mean that b and h2 are related by an edge in H (and similarty for 91 ~ 92). Note that if one of G and H is empty, then the box product is empty.
There is natural coloring on GUH where a vertex hg E V(GDH) is assigned the color (c(g), c.h)). For simplicity, we will view (C1, and (C2, 01) as the same color for all 0ı C2 E X. Unless mentioend otherwise, vertex-level (resp. edge-level) color- filtration GOH is always taken to be with respect to the product color structure above.
Motivation 1. Graph products provide natural model to convert database analysis questions to inputs for GNNs. For example. suppose one has two tables Table A is the wage income of residents in New York, and Table B is the wage income of residents in London, with some additional demographic / financial information for both. For each table, we can view the rows as nodes and assign similarity metric the rows such that two nodes with sufficient similarity are linked with an edge. Suppose our goal is to compare the residents in New York against the residents London, then one natural operation would be to take the Cartesian product of the tables, call this new table Table C. A reasonable graph one can make out of Table C is as follows- the nodes are still the rows. For person X in Table A paired with person Y in Table in order analyze how X compares with Y and those similar to Y, we ought to look at how X connects with everyone in Table B that are connected to Y under the similarity metric before. What this means terms of graphs is that we should link the node (X, Y) to (X, Y') for all Y' that is linked to Y. We can also do this symmetrically, which produces exactly the box product of Table and Table B.
We can define PH and EC on graph products with respect to the color-based filtrations in Definition 5. We wish to examine whether the graph product contains information that the components do not give. Given two graphs G and H and suppose for contradiction that they are isomorphic, then it follows that their products GDG, GDH, and HOH are all isomorphic graphs. If we could show that any two product graphs in the triplet are not isomorphic, then G and H are not isomorphic.
In the case of PH, the graph product does capture structure not seen by the individual components. Proposition There exist graphs and H such that PH cannot tell apurt, but PH can tell apart GDG and HOH. Furthermore, an example is given in Figure 1.
H
GDG
HOH
(A)
(B)
Figure 1: Graphs G and H that vertex-level and edge-level PH cannot tell apart, but they can be differentiated by running edge-level PH on GLG and HНН. Here, connecting the edges between vertices of color (blue, blue) and (red, blue) creates a non-trivial cycle in (A) and no cycles in (B).
The EC, on the other hand, does not obtain any more expressivity over the product filtration. Proposition S. Let G and H be graphs with the same number of vertices. If EC cannot differentiate G and H, the EC diagrams for GUG, GOH, and HUH are also all the same.
The proof of Proposition 5 comes from a direct application of Theorem 2, as we will show in the Appendix that GLG, HOH, and GDH all have the same combinatorial data in the statement.
5

---

In light of Proposition 4, a natural question to ask is can the PH of the product contain strictly more information than the PH of the two components? The answer guaranteed be yes if we adjoin "virtual node" in the following sense.
Definition Let G = EV, c, X) be a graph, we define G+ as L {+) where * is disjoini basepoint and we define (x())= virtual and (x(x) = clz) all x E X. For any color-based filtration of G4, we also require the vertex to be born at time -o (ie. appears before any other vertices).
E, c, E,
(virtual))
With the example given in Proposition 4, we have the following corollary.
Corollary 1. Let G and H be graphs, then the PHI of G G+DH4, H4 + contain strictly more information then PiI of G and H.
In other words, taking the PH of "virtual" graph products contain strictly more information than comparing the PH of each component. We remark that the EC of "virtual" graph product still would not add more information. This is because if graphs A and have the same EC diagram for all possible filtrations, does A and B allowing to apply Proposition 5.
5 Product Filtrations
In this section, we focus on a strict subset of possible filtrations on the graph product. Given graphs G' and H, we investigate what information about the graph product GOH can be recovered from filtrations on G and H alone. Formally, we want to consider filtrations of the following form. Definition 7. Let G and H be graphs with filtration functions fo and f respectively. We can define a product filtration of GDH with respect to the two filration functions as the following let E IR then the subgraph (GDH), b is exactly G GH
5.1 Characterization of Vertex-leve and Edge-level Product Filtrations
The two notable forms of filtrations on G and H we want to consider are vertex-level and edge-level filtrations in the sense of Definition 1. Here, we give a characterization their respective product filtrations in terms convenient coloring on GDH.
Proposition Suppose fG and fH are injective vertex color functions. The product filtration with respect to fa and fH is equivalent to the filtration on GOH given by the vertex coloring function F, where F((g, = max (((())((())) JH)),H(((C)) (c(c)))),, for all (g, h) E (GDH), In particular, this implies that the persistence diagrams of this product filtration filratttn are well-defined. We write F = fo05 when the context is clear.
Proposition 7. Suppose fc 0 and fa 0 are injective edge color functions. The product productfiltration
with respect to fc and fa is equivalent to the filtration on GOH given by the function F where where F sends all vertices to 0 and for all ((g1, h1), h1), h2)) E E(GDH). F(e) fa (c(h1). c(h2)) if 91 = 92 and F F(e) fa ffacclg (c(g)). c(gg)) if h1 = h2- Note that 91 = 92 and by = h cannot both be satisfied simple graph. We write F fo0 when the context is clear.
5.2 Computational Methods for Product Filtrations
In this section, we discuss algorithmic procedures to compute the PH of the vertex-level and edge- level persistence diagrams. The computational methods we obtain for I-dimensional persistence diagrams is more general, so we will discuss them separately. Note that although we used color-based filtrations in the expressivity analysis above, the algorithms devised here applies to any pair of filtrations. For graph G, we my and ng the number of vertices and edges respectively.
Following Proposition 6, we can in fact obtain an algorithmic procedure to keep track of how the 0-th dimensional persistence diagram of GOH changes under the product of vertex filtrations.
Theorem 4. Let (G, fa), (H, fu) be two vertex-based filtrations, then the O-dimensional PH diagram for (GDH, fu] can be computed using Algorithum 1. This can be equivalently be computed by Algorithm 3 in the Appendix. The runtime is O + mg log mG + mH log m + ng + nH), assuming the coloring set has constant size.

---

We remark that the runtime complexity in Theorem 4 is more efficient than the naive method. A naive calculation for vertex-level product filtrations would be to rum PH on the entire graph product directly. This incurs a runtime of ( + (ngmu + RL n (lg + -)mm)))) This is because, by the discussions before 4.1 of [24], the PH connected graph with r edges can be calculated in Orr log(r)) time. If the graph is not connected, the runtime is O(s + r log(r)), where is the number of vertices, to account for the worst-case scenario where the graph is totally disconnected. We demonstrate the runtime benefits of Theorem 4 empirically later in Figure 3.
We now describe a concrete example of computation using Algorithm 1 outlined in Theorem 4.
Example 1. Consider the graphs G = H in Figure 2. and let ag = fo (blue) < <a = fu (red). Here we take fc = fH fu. Observe that both G and H' 'ss individual filtrations proceed by spawning two blue vertices at dg and completing to the entire graph at a1 We would like to compute the O-dimensional PH of the product of vertex filtrations. Before the for-loop, we initialize 16 -eath- pairs with 4 copies of (ao.-) and 12 copies of (a1.-) (we omit their vertex representatives for simplicity).
We start with t = ag. Note that since we removed -oo before the loop, the index 1 elements in the precomputed lists correspond to the relevant values al time ug- Since there are no deaths either G or H at dg, we skip the two internal for-loops. bettH(0) is empty (since this is recorded at -oc). and bettig [1] x births [L] represent the blue vertices and there are no non-trivial deaths. We then mark all tuples that are not the 4 blue vertices with birth time to die at ag, but there are no such tuples. Thus, we conclude that nothing happens at Og-
At t = 01, 2 red vertices and blue vertex die for both G and H. Only the blue vertex death is non-trivial, so in the first inner for-loop we mark 2 of the blue vertices in GDH die (ag, a1). ) In the second inner for-lopp one of the blue vertex is marked already, and we mark another tuple to (ao, 01). This produces copies of (ao, 01) ). There are no non-trivial births at this stage, so we mark all vertices born at an to die at a,, which makes 12 copies of (0),
Art t +00, the final blue vertex dies for both G and H. so we mark the final vertex in GDH die as (oo. oo). There are no non-trivial deaths, and also no remaining tuples to fill out, so we stop.
Algorithm 1 Computing the O-dim PH Diagrams in Product of Vertex-Level Filtrations
Input: The vertex-level filtrations (G, fa) and (H, fH)
Output: The O-dim PH diagram for (GD fclfH)
1: impla. implæ <- O-dim PH diagrams for (G, fa) and JH)
2: Iltration_stepe +- [ooo]u filtration steps for fc and fH U(+oo), and ordered.
3: birthsc, births +- list of tuples born non-trivially in G (resp. H) at each time in filtration Eltrrationsteps..
4: bettig, betti < list of vertices alive representing components of the subgraph of G (resp. H) at each time in filtration sttoosssstsssssott
5: deathse, deaths +- list of tuples that die non-trivially in G (resp. H) at each time in
6: Remove (- (-o0) from filtrationsstant steps.
7: output < [(V, ma None) for (i,j) in V(G) x V(H).
8: for in [0. len(filratioon_teps)) do
9: a; < -fitrraioo_steppe
for in deaths + do
>
Marking Non-Trivial Deaths
11:
Mark all tuples in output with p|1] = v,p,2] < 0;,p = None with p[3] + aç.
12:
for in deaths
do Mark all tuples p in output with p(0] = w. p[2] < a, p(3 = None with p(3] <- 0z.
Marking Non-Trivial Deaths
13:
14:
ni nirths +- birthsa + 1] x betti [1] + beltigli + 1] x birthsn + 1].
15:
nt_deaths <- births [ + x deathsn i
16:
nt_ bibbithss <- nt_births ni_deaatss.
17:
Mark all tuples p in output with (p(0).p(1)) & nt birbirths p/2] = o, 0..p(3] None with Marking Trivial Deaths
p[3] +- 0,.
return [(p[2), p(3)) for p in output]
7

---

O> O fe(red) > f. f.(blue)
f.(bue)
fo(red)
f.(red)
Adding Changes
Adding Changes
Figure 2: The product of the vertex filtrations on G H given by (red) > fo (blue). See Example for how the algorithm in Theorem is used to compute the PH of this filtration.
Now we describe an algorithm for the 0-th dimensional persistence diagram of the product of edge filtration. Since all vertices are born the same time in this filtration, suffices for to keep track of the number of deaths at each time.
Theorem 5. Let (G), (H, be two edge-based filtrations. The O-dimensional PH diagram for (GDH, can be computed using Algorithm 2. The runtime is (mmax(n log ng ng log ng, mg log mg ng. my log my + ng)).
The runtime Theorem 5 again an improvement over the naive case, which is O ngma (ogaa)lg(GGmmm + ngmg)), and we empirically assess their performance in Figure 3. We give a computational example using Theorem in Example the Appendix. Finally, we describe procedure calculate the 1-dimensional persistence diagrams for general product filtration.
Algorithm 2 Computing the O-dim PH Diagrams in Product of Edge-Level Filtrations
Input: The edge-level filtrations (G, fc 2 0) and (H, JH 2 0)
Output: The 0-dim PH diagram for (GDH, fH)
1: imple. implμ + O-dim PH diagrams for (G, fa) and (H, fH).
2: filtration_steet steps {-o0) JJ filtration steps for fo and fH Uf Uf+ and ordered.
3: deathsg, deaths < list number of vertices that die at each time filtration_see peteratiionstpps...eee stepss
4: still till_aliveg, stlllaliven list of number of vertices that still alive each time in filtration_steps
5: Remove (-oo] from filtration_stepy stteps.
6: output= [
7: for in [0. len(filrration_stet
do
8: a; < celtration_steps_Pe
9: num seil__aivee, dil-dhats + 1] still aliveeli 1e-thah (i 1].
10: output += [(0, a;) for in range(O,, num)]
11: return output
Proposition 8. Let {Gr} and {H₂} be two filtrations of G and H respectively. Consider the induced filtration on GDH given by (GOH); = G,OH,, and let a < 02 < <... On mark the times where (GDH); changes. The !-dimensional PH of this filtration is exactly the data of 31 (G DH copies of (a1, 00) and (G,G (H,, O log mc (AUI) = # E(E (EA)) (o(A))((B) (B)
B1 BI(Ga,- (HHa.)) copies of (a,, oo) for i >> 1. The runtime is m- log mH + nH) because, for any two graphs and B, we may compute
Limitation. The algorithms presented here only cover subcollection of possible color-based filtrations on the graph product GDH. general, for filtration on GDH that does not arise from the product of filtration on G and H, there is reason to expect the PH for the filtration on GDH can be neatly decomposed similarly the algorithms in this section. Computing PH on graph products with color-based filtrations outside of product filtrations may be more computationally expensive.

---

Table 2: Accuracy Results: Standard PH vs. PH on graph products (GProd) on pairs of Cayley Graphs
and three datasets from the BREC benchmark. We use filtrations induced by three functions: edge closeness, Jaccard index, and square clustering coefficient. Overall, persistent topological descriptors computed on graph products yield improved performance in distinguishing non-isomorphic graphs.
Minimal Cayley Graphs
BREC Datasets
Filtration
Method
c-12
c-16
e-20
c-24
c-32
c-36
C-63
Basic (60)
Reg. (50)
Ext. (100)
PH
100.0
100.0
100.0
99.85
99.93
99.93
100.0
93.33
86.00
71.00
Closeness
GProd
100.0
100.0
100.0
100.0
99.93
100.0
100.0
100.0
100.0
94,00
Jaccard Index
PH
95.24
83.33
60.71
85,59
76.50
84.33
73.33
98.33
94.00
56.00
GProd
95.24
83.33
60.71
85,59
76.50
84.33
73.33
98.33
94,00
61.00
Clustering
PH
100.0
100.0
100.0
95.80
97.64
96.52
82.50
100.0
98.00
84.00
GProd
100.0
100.0
100.0
97.00
97.64
97.31
90.00
100.0
98.00
84.00
6 Experiments
To evaluate the empirical power of topological descriptors for graph products, we run three sets of experiments. The first investigates their effectiveness on BREC datasets [49] and minimal Cayley graphs [11] with varying number of nodes, which are popular benchmarks for assessing the expressive power of graph models. The second examines the runtime performance of the algorithms described in Theorems 4 and 5, using the BREC datasets. Finally, the third demonstrates how these descriptors can be integrated with GNNs for graph classification tasks.
Expressivity. For two input graphs G and H, we use graph products to decide isomorphism as follows.
1. Compute the persistence diagrams for GLG and GUH. If the diagrams differ, we conclude that G and H are not isomorphic. Otherwise, proceed to Step 2.
2. Compute the persistence diagrams for GDG and HOH. If these diagrams differ, again conclude that G and H are not isomorphic. If they are identical, the test is deemed inconclusive -i.e., G and H are considered isomorphic by this test.
Following this strategy, we compare our method (GProd) against standard PH (with vertex and edge filtrations), considering three filtration functions: edge closeness centrality, Jaccard index, and square clustering coefficients. Details regarding these functions are given Appendix
Table 2 presents accuracy results. Overall, computing topological descriptors on graph products outperforms the standard approach (i.e., applying PH the original graphs), although the two methods perform identically on several datasets. Even without introducing virtual nodes (see Corollary 1), the standard approach does not achieve higher accuracy in any of these experiments.
Runtime. For the vertex-level product filtration, we consider three algorithms: (i) our proposed method (Theorem 4): (ii) naive computation on the full graph product using the union-find PH implementation described in Algorithm 1 of [26]: and (iii) a naive computation using the persistent homology routines from the gudhi library [39]. Similarly, for the edge-level product filtration, we compare three counterparts: our method (Theorem 5), a union-fing PH implementation on the graph product, and the gudhi-based approach. We provide implementation details in Appendix E.
We evaluate all algorithms using BREC datasets. For each pair of graphs G and H, we apply vertex/edge-level filtrations and compute the persistence diagrams of GOH. Figure reports the average runtime (in seconds, taken over 10 trials) each algorithm took to go over the entire dataset. Notably, as the graph sizes increase, Theorems 4 and 5 significantly outperform the other two methods.
Graph classification. We employ the following procedure for integrating descriptors based on graph products into GNNs for graph-level classification tasks. First, we select diverse set of reference (or anchor) graphs, such as cycles, random graphs, and complete graphs. Then, for a given input graph G and choice of filtration function, we either compute the product filtration between G and each reference graph or obtain a filtration directly from their product. This process yields as many persistence diagrams as reference graphs. The resulting diagrams are then vectorized using an
For full transparency, we note that Table differs from earlier versions of the paper due to a bug our code that incorrectly reported perfect accuracy for GProd. As a result, we revisited the experimental setup and considered alternative filtration functions and additional datasets to better illustrate the expressivity gains of our approach. We provide further details in the official code repository and in Appendix E.

---

Runtime (Vertex-based)
Runtime (Edge-bused)
10F
Anerag nurkine ix log soal)
Theorem 4 tours)
Ancrage nor inst Is. lag scle)
Theorem (ours)
Union
yodli
100.5
gulbi
36.5
24.1
31.
22.6
31.3
000
1.5
1.5
22
10f
0.9
14
7.0
Baskc
STR
DR
CFI
Biolc
STR
DR
CRI
Figure 3: Average runtime (in sec.) of different implementations of topological descriptors for graph products. Our algorithms (Theorems 4 and 5) consistently outperform previous implementations.
appropriate embedding scheme [8]. Finally, the topological embeddings are concatenated with the GNN ones and passed through a classification head. In this work, we employ seven reference graphs generated using the NetworkX library [20]. Also, we apply the Gaussian vectorization scheme [8]. We refer to Appendix E for further details.
In order to assess the effect of integrating topological descriptors, based on graph products, on the performance of GNNs, we consider two variants. GProd consists of computing PH on the box product of two graphs; ProdFilt consists of computing (vertex) product filtrations (as in Algorithm 1). In addition, we consider three GNN architectures: GIN [50], GCN [32], and GraphSAGE [21]. Each model uses a hidden dimension of 64, and the optimal number of layers (chosen from 2, 3, 5) is selected based on validation performance. For the graph product descriptors, additionally treat the filtration functions (degree and betweenness centrality) as hyperparameters.
We consider six real-world popular datasets for molecular property prediction: COX2, DHFR, NCI1, NCI109, ZINC (12K), and PROTEINS [12, 30J. All tasks are binary classification, except ZINC, which is regression dataset. For ZINC, we use the publicly available train/validationntess splits: for the remaining datasets, we adopt random 80/10/10% split. Further details on datasets, hyperparameter selection, and model configuration are provided in the supplementary material. We compute the mean and standard deviation of the performance metries (MAE 4 for ZINC, and accuracy for all other datasets) over five runs with different seeds.
Table 3: Graph classification results. The inclusion of topological descriptors derived from graph products leads to consistent improvements in the predictive performance of GNNs.
Model
DHFR 1
COX2
PROTEINS 1
NCII 1
NC1109 1
ZINC +
GIN
80.53 + 4.10
76.60 = 2.61
70.18 = 5,11
80.19 :\2 1.83
78.74 1: 1.65
0.57 = 0.02
GIN GProd
82.89 + 4.16
78.30
73.04 491
81.65 : 2.42
80.97
1.82
0.54 0.02
GIN ProdHit
81.58 + 2.79
78.72
3.36
72.50
3.54
80.19
1.08
80.15 2.47
0.54 0.02
GCN
78.68 + 5.54
79.15 3.81
73.04 = 2.92
79.12 + 1.07
79.08 + 1.95
0.64 0.08
GCN GProd
83.95 +: 5.38
75.32 = 3.87
73.75 = 5.70
79.71 + 1.64
80.00 1 1.10
0.62 0.01
GCN ProdFilt
80.00 + 8.99
80.85 = 6.73
74.11 = 3.28
79.90
0.82
80.53
1.23
0.62 0.01
SAGE
84.21 + 3.48
76.17 = 0.95
72.86
1.62
78.98 + 0.94
79.81
1.31
0.51
0.01
SAGE GProd
83.16 1:: 40
80.85 2.61
71.43
3.40
80.29 0.75
78.50
3.16
0.48
0.01
SAGE ProdFilt
84.21 + 2.63
77.87 + 4.41
73.21
5.79
80.00 + 1.09
79.66
1.41
0.48
0.01
Table 3 reports the results. Overall, incorporating topological descriptors leads to best performance for most GNN/dataset combinations. Also, there is no clear winner between GProd and ProdFilt, tlt, and they yield the same performance on ZINC (the largest dataset). These experiments show that combining expressive topological features with GNNs can lead to consistent empirical improvements.
7 Conclusion and Broader Impact
We characterized the expressive power of EC on general color-based filtrations, and introduced more efficient variant that has the same expressivity. We also examined the interaction of both EC and PH with graph box products, establishing contrasting results in terms of their respective benefits over the EC and PH of individual components. Furthermore, we devised efficient algorithms to compute persistence diagrams for sub-collection of filtrations arising from the product of vertex-level, and edge-level, filtrations. Our experiments demonstrated consistent empirical gains. As graphs are ubiquitous in many real-world scenarios such as molecules, recommendation systems, and multi-way data, envision that this work would open several avenues for applications in multiple areas.
10

---

Acknowledgments and Disclosure of Funding
This research was conducted while the first author was participating during the 2024 Aalto Science Institute international summer research programme at Aalto University. We also acknowledge the computational resources provided by the Aalto Science-IT Project from Computer Science IT. We are grateful to the anonymous program chair, area chair and the reviewers for their constructive feedback and service. VG acknowledges the Academy Finland (grant 342077), Saab-WAST (grant 41 1025), and the Jane and Aatos Erkko Foundation (grant 7001703) for their support. AS acknow ledges the Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) (312068/2025-5)
MJ would like to thank Sabína Gulčíková for her amazing help Finland in Summer 2024. MJ would also like to thank Cheng Chen, Yifan Guo, Aidan Hennessey, Yaojie Hu, Yongxi Lin, Yuhan Liu, Semir Mujevic, Jiayuan Sheng, Chenglu Wang, Anna Wei, Jinghui Yang, Jingxin Zhang, an anonymous friend, and more for their incredible support in the second half of 2024.
References
[1] Mchmet E. Aktas, Esra Akbas, and Ahmed EI Fatmaoui, Persistence homology of networks: methods and applications. Applied Network Science, 4(1):61, 2019.
[2] Rubén Ballester and Bastian Rieck. On the expressivity of persistent homology in graph learning. arXiv e-prints 2302.09826, 2024.
[3] Guy Bar-Shalom, Beatrice Bevilacqua, and Haggai Maron. Subgraphormer: Subgraph GNNs meet graph transformers. In NewrlPS 2023 Workshop: New Frontiers in Graph Learning, 2023.
[4] Guy Bar-Shalom, Yam Eitan, Fabrizio Frasca, and Haggai Maron. A flexible, equivariant framework for subgraph GNNs via graph products and graph coarsening. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
[5] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Liò, Guido Montufar, and Michael M. Bronstein. Weisfeiler and lehman go cellular: CW networks. In Advances Neural Information Processing Systems (NeurIPS), 2021.
[6] Cristian Bodnar, Fabrizio Frasca, Yu Guang Wang. Nina Otter. Guido Montúfar, Pietro Liò, and Michael Bronstein. Weisfeiler and lehman go lopological: Message passing simplicial networks. In International Conference on Machine Learning (ICML), 2021.
[7] Davide Buffelli, Farzin Soleymani, and Bastian Rieck. CliquePH: Higher-order information for graph neural networks through persistent homology clique graphs. In The Third Learning Graphs Conference, 2024.
[8] Mathieu Carriere, Frederic Chazal, Yuichi Ike, Theo Lacombe, Martin Royer, and Yuhei Umeda. Perslay: A neural network layer for persistence diagrams and new graph topological signatures. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
[9] Yuzhou Chen, Baris Coskunuzer, and Yulia Gel. Topological relational learning on graphs In Advances Neural Information Processing Systems (NeurIPS), 2021.
[10] Zhengdao Chen. Lei Chen. Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? In Advances in Neural Information Processing Systems (NeurIPS). 2020.
[11] K. Coolsaet, D' D'hondt, and Goedgebeur. House of graphs 2.0: database interesting graphs and more. Discrete Applied Mathematics, 325:97-100 -077 2023.
[12] 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):1-48, 2023.
[13] Herbert Edelsbrunner and John Harer. Persistent homology survey. Contemporary Mathematics, page 257-282, 2008
[14] Aref Einizade, Fragkiskos D. Malliaros, and Jhony H. Giraldo. Continuous product graph neural networks. In Conference on Neural Information Processing Systems (NeurIPS), 2024.
[15] Yam Eitan, Yoav Gelberg, Guy Shalom, Fabrizio Frasca, Michael Bronstein, and Haggai Maron. Topological blind spots: Understanding and extending topological deep learning through the lens of expressivity. In International Conference Learning Representations (ICLR), 2025.
11

---

[16] Zhenyao Fang and Qimin Yan. Leveraging persistent homology features for accurate defect formation energy predictions via graph neural networks. Chemistry of materials: publication the American Chemical Society, 37(4):151-11540 2024.
[17] Fey and Lenssen. Fast graph representation learning with PyTorch Geometric, Workshop track of the International Conference on Learning Representations (ICIRR), 2019.
[18] V. Garg, S. Jegelka, and T. Jaakkola. Generalization and representational limits of graph neural networks. In International Conference Machine Learning (ICML), 2020.
[19] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. International Conference on Machine Learning (ICML), 2017.
[20] Aric A. Hagherg, Daniel A. Schult, and Pieter Swart. Exploring network structure, dynamics, and function using networkx. In Proceedings of the 7th Python in Science Conference, pages 11 - 15, 2008.
[21] William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
[22] Allen Hatcher. Algebraic Topology. New York: Cambridge University Press, 2002.
[23] Akihito Hora and Nobuaki Obata. Hamming Graphs, pages 131-146. Springer Berlin Heidelberg, Berlin, Heidelberg, 2007.
[24] Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borgwardi, Topological graph neural networks. In International Conference on Learning Representations (ICLR), 2022.
[25] Nohuhiko Ikeda, Paul Watta, Metin Artiklar, and Mohamad H. Hassoun. two-level hamming network for high performance associative memory. Neural Networks, 1499):119--1200, 2001.
[26] Johanna Immonen, Amauri Souza, and Vikas Garg. Going beyond persistent homology using persistent homology. In Advances in Neural Information Processing Systems (NewrIPS), volume 36, 2023.
[27] Wilffied Imrich and Sandi Klavžar. Product Graphs: Structure and Recognition. John Wiley & Sons, New York, 2000.
[28] John J. Irwin, Teague Sterling, Michael M. Mysinger, Erin S. Bolstad, and Ryan G. Coleman. Zine: A free tool to discover chemistry for biology. Journal of Chemical Information and Modeling, 52(7):1757-1768. 2012.
[29] Sai Kiran Kadambari and Sundeep Prabhakar Chepuri. Product graph learning from with sparsity and rank constraints. IEEF Transactions on Signal Processing, 69:5665-5680, 2021. doi:
data
10. 10
[30] Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Benchmark data sets for graph kernels, 2016. URL http:://graphikernell.s cs. tu- aa-dortmundd..r tmund.de. de.
[31] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
[32] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017. 2017.
[33] H. Maron, H. Ben-Hamu, H. Serviansky, and Lipman. Provably powerful graph networks. Advances in Neural Information Processing Systems (NeurIPS), 2019.
[34] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. F. Lenssen, G. Rattan, and M. Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI Conference Artificial Intelligence (AAAI), 2019.
[35] Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Ricck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: the story so far. Journal of Machine Learning Research, 24(1), 2024.
[36] Viet The Nguyen, Duy Anh Pham, An Thai Le, Jans Peter, and Gunther Gust, Persistent homology-induced graph ensembles for time series regressions. arXiv preprint Xiv:25003.14200 2025.
12

---

[37] Theodore Papamarkou, Tolga Birdal, Michael M. Bronstein, Gunnar E. Carlsson, Justin Curry, Yue Gao, Mustafa Hajij. Roland Kwitt, Pietro Lio. Paolo Di Lorenzo, Vasileios Maroulas, Nina Miolane, Farzana Nasrin, Karthikeyan Natesan Ramamurthy, Bastian Rieck, Simone Scardapane, Michael T Schaub, Petar Veličković, Bei Wang. Yusu Wang, Guowei Wei, and Ghada Zamzmi. Position: Topological deep learning is the new frontier for relational learning. In International Conference on Machine Learning (ICML), 2024.
[38] Mathilde Papillon, Sophia Sanborn, Mustafa Hajij. and Nina Miolane. Architectures of topological deep learning: A survey on topological neural networks. ArXiv e-prints, 2023.
[39] The GUDHI Project. GUDHI User and Reference Manual. GUDHI Editorial Board, 3.11.0 edition, 2025.
URL https: //gdhi. inriii a. wtw.frr////////aaoooooooooo 11. 1../.
[40] Bastian Rieck. Topology meets machine learning: An introduction using the euler characteristic transform. arXiv e-prints, 2024.
[41] Joshua Robinson, Rishabh Ranjan, Weihua Hu, Kexin Huang, Jiaqi Han, Alejandro Dobles, Matthias Fey, Jan Eric Lenssen. Yiwen Yuan, Zecheng Zhang, Xinwei He. and Jure Leskovec. Relational deep learning: Graph representation learning relational databases. In NeurIPS 2024 Third Table Representation Learning Workshop, 2024.
[42] Ernst Röell and Bastian Rieck. Differentiable Euler characteristic transforms for shape classification. In International Conference on Learning Representations (ICLR), 2024.
[43] Mohammad Sabbaqi and Elvin Isufi Graph-time convolutional neural networks: Architecture and theo- retical analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(12):14655-1463, 2023.
[44] Samal, R. Sreejith, Gu. S. Liu, Saucan, Jost. Comparative analysis of two discretizations of ricci curvature for complex networks. Scientific Reports, 8(1):6650, 2018.
[45] Aliaksei Sandryhaila and Jose M.F. Moura. Big data analysis with signal processing on graphs: Represen- tation and processing of massive data sets with irregular structure. IEEE Signal Processing Magazine, 31 (5):80-90, 2014.
[46] Katharine Turner, Sayan Mukherjec, and Doug M. Boyer. Persistent homology transform for modeling shapes and surfaces. Information and Inference: A Journal of the IMA, 3(4):310-344, 2014.
[47] Yogesh Verma, Amauri H Souza, and Vikas Garg. Topological neural networks go persistent, equivariant, and continuous. In International Conference on Machine Learning (ICMI.).
[48] Julius von Rohrscheidt and Bastian Ricck. Diss-I-ECT: Dissecting Graph Data with local Euler Character- istic Transforms. In International Conference on Machine Learning (ICML), 2025.
[49] Yanbo Wang and Muhan Zhang. An empirical study of realized GNN expressiveness. In International Conference on Machine Learning (ICML), 2024.
[50] K. Xu, W. Hu, Leskovec, and S. Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019.
[51] Qi Zhao, Ze Ye, Chao Chen, and Yusu Wang. Persistence enhanced graph neural network. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
13

---

A Proofs
A.1 Proofs for Section
We treat the proof of Proposition
separately in Appendix B.
A.2 Proofs for Section
In this section, we will characterize the expressivity of EC on graphs. For the discussion of EC on simplicial complexes, please see Appendix D.
Before we state the proofs, we first remind the reader that in Section 3, we assumed that G and H have the same number of vertices (otherwise, they clearly not isomorphic each other).
Remark 1. This assumption on G and H also gives justification for why our definition of FC(G, f) does not include the Euler characteristic of Gb., as that is just the number of vertices on the graph.
Proof of Proposition 2. We will first show that the second and third items are equivalent. For each vertex color function f I, we use gf X X - to denote its correspondent edge color function.
Suppose F.C (G, F.C (H, for all possible f X - IR. Recall by assumption G and H have the same number of vertices n. Let f be an vertex color function such that 0 < f(a) < f(b) < min f(;), then we have that
n-#Eola, a) X(G))) ) #E
Hence # Ea a) # a). By choosing another appropriate vertex color function, we can similarly show that # (b, = En (b, b). Now, if we look back on the function f, we have that
#a a) # (a, =Fbb(bb) x(G
=
EH - #En b) - EHH (b, b).
This implies that #E b) = # # (a. since already know that # EElaa a) #EH
and # #c.(b, # E'H (b, b).
Conversely, suppose #E (a, b) # En (), for all colors a, X. Let f be edge color filtration function such that < f(1)) S S fdd), where d, is relabeling of the colors cI,...
by this ordering.
= n Since G and H have the same number of vertices n, we have that )
x(Hg'). Thus,
suffices for us show that x(G x(H for all t O. Indeed,
x(G =
Σ
#Eo(dr,d))
iSj st ((4))
=
Σ
(d,(d,,
Kj (()))())
Hence, we have that the second and third items are equivalent. Finally, we observe that clearly (1) implies (2) because the edge function induced by the max EC diagram is special case of symmetric edge coloring function. An argument very similar to the proof of (3) implies (2) will also show that O,
(3) implies (1). This is because for all
x(G))=
= =
Σ
#F dg)
$ st. dsd
Σ
#EH (d, d,)
S st. ds)
= =
14

---

Proof of Proposition 3. There is no difference between the definition of the 0-th dimensional compo- nent of the EC diagram and the max EC diagram, so the first two items are equivalent.
For (1) implies (3), we can choose any injective vertex color function such that f obtains its minimum at the color c, Then G f(c) and H flc) will be G(c) and H()), and hence their Euler characteristics will be the same. For any # b E X, we can choose an injective vertex color function such that is smallest at a and second smallest at b. In this case, we have that
X(G = x(H
Here have that
X(G/ (00) = x(G(a)) - #Ea(a, b) X(G(b))
x(H) (()) = x(H(a)) - #En (a, b) X(
Hence, we conclude that # (a b) #En (a,b) for all # E X. The proof of (3) implies (1) is similar to that in Proposition 2.
Proof of Theorem 2. The first two statements come directly from combining the statements of Propo-
sition 2 and Proposition 3. The third statement follows from the observation that (G(())
# #Ea c) = (Vc(c).
A.3 Proofs for Section
Proof of Proposition 4. The proof for why edge-level PH can differentate GDG and HCH is mainly self-explanatory by the caption of Figure 1. The reason why edge-level PH is able to differ GDG and HOH is because when adding the edges between (blue, blue) and (red, blue) creates a cycle for GLG and does not change the I I-dimensional persistence diagram for HOH.
To see why PH cannot tell apart G and H individually. We first note that there are no cycles, so we only need to focus on the O-th dimensional components.
Write r (red) and b = fu (blue). If b, then their persistence diagrams the same since G and H have the same number of vertices and connected components. If b >> r. then the subgraphs G, and H, are exactly the same graph, so PH cannot tell that step apart. At / = b. for both G and H, two blue vertices are born and deceased the same time, and one red vertex is also killed. If r > b, then again G3, and Hs are isomorphic graphs. At = r, for both G and H. two red vertices are born and dead at the same time, and one blue vertex is also killed. Thus, we conclude the vertex-level PH cannot tell apart G and H.
For vertex-level PH:
For edge-level PH: Write a = (red, red) and b fe (red, blue). If b, then they have the same persistence diagrams because G and H have the same number of vertices and connected components. if b, then there are two deaths that occur l b and one death at L a for both graphs. If b > o, then there is one at / = a and then two deaths are / = for both graphs. Thus, we conclude the edge-level PH cannot tell apart G and H.
Proof of Proposition 5. For two general colored graphs A and B. For colors a, b E X, we observe that #VADB( b)) = #Vx(O)#VV()) + #Va(a)+VVau) (here the second term is due to the symmetry assumption).
For colors (a, b), (c. d)
X x X, we also wish to enumerate # #Exno b). (c,d), d)). Indeed, without loss when both a & and a a d. the definition of box product indicates that # Aannaaaaaaa (a, b), (c. d)) = The axioms for the box product indicates that edges can only occur between two pairs of colors that share at least one color in common. By rearranging the order of tuples if necessary, we without loss only need to enumerate # #EACB((a, ( (a, d)). If b # d, then the number is given exactly as
# EACB (a. (a, d)) #V d) + #VB (a) (b,
Now since G and H in the statement of the proposition have the same EC diagram for all possible filtrations, Theorem implies that for all cı, C2 E X, #Va(c)) = # (c1) and # #Ea(c1 02) = # E (c), Plugging this equality into the formulas derived above, we have that
#Vona b)) #VOOH ((a, b)) = +VHou((a, 6)),
15

---

#E ((a, b). (c, d)) = = #or ((a, b), (c, d)) = # En ((a, b), dc)
for all possible choices of colors. Thus, Theorem 2 implies that GDG, GDH, and HOH all have the same EC diagrams for possible filtrations.
L
Proof of Corollary 1. We first observe that for any two graphs A and B, we have that
A, - (A U B Bu ADB))
When A B G from the statement of this corollary, observe that
G+DG+ = (GLLU
Write the two disjoint copies of G produced here Gu- Observe that each vertex E Go (or G1) has the color (c(v), virtual). Observe that no vertices in GDG has the color that has the tag virtual in it, so
choose coloring procedure such that we go through the filtrations Go and 11 first before going through GDG. Running vertex-level (resp. edge-level PH) through this coloring procedure, we will produce two copies of vertex-level PH (resp. edge-level PH) for G, which recovers the original information. A similar procedure also works for H. Thus, the PH of G, GHH, HHt has least much information the PH of G and H. The part for "strictly more information" follows from Proposition 4.
A.4 Proofs for Section
Proof of Proposition 6. To check that the graphs are the same, we wish to check that they have the same vertex set and edge sets. Indeed, let & IR then
VIG!CHH(") ((g, fa < and (c(()))) S
h(g
(( 1 {(g,h) h() S () V(GDDH)))
Now check edges, we have that for (g1, 41), (g2, h2) (G,UH, V(GGLH)) Now suppose there is an edge between (g)/),) and (g2, h2) in (GDH) C GOH. Since this an edge in GDH it means either of two following cases
1. 91 = 92 and h1 h2 H. Now if we can show that h1 ~ h2 in He, then this will give an edge between (g1, h1) and (g2, h2) in Gf Indeed, that just comes from the definition of vertex filtration as the colors on h1, h22 are both less than or equal to / under Jn-
2. h2 and 9i 92 in G. The argument is nearly identical the first case.
Conversely, suppose there is edge between (g1, h1) and (92, h2) in G!*DH!". Then, since F((g,,)) < and F((g2, fz)) I (as they have the same vertex set), it follows that this edge has to be in (GDH), by definition of vertex filtration.
Li
Proof of Proposition 7. To check that the graphs are the same, we wish to check that they have the same vertex set and edge sets for all t 2 0. The vertex set at time t for > 0 is always the collection of all vertices. The proof for the edge sets follows similarly to the proof in Proposition 6.
Now we will prove that the outputs of Algorithm and Algorithm 2 gives the O-dimensional PH diagrams for the product vertex-level filtraitons and edge-level filtrations respectively. For Theorem 4 and Algorithm we also note that there is more symmetric presentation of Algorithm 1 in terms of Algorithm 3, which we will show gives the same output. We now proceed to prove Theorem 4.
Proof. For Algorithm Output: We first observe that we modify nt deaths Algorithm I to be defined as nt dea_ts bettigli + 1] deaths [i + 1J. then it would give the same output. This is because every vertex in birthsg + 1] is in bettiglt + 1] (with compati- ble representatives), and subtracting the two versions of nt deaths from births would still give the same set (since the intersection of nt nt_bbittss with their respective complements are the same).
From here, showing that Algorithm produces the correct output equivalent to showing the following theorem.
16

---

Theorem 6. In the set-up of Proposition 6. mark all the times G changes as do <... < On Let b, (G) and GG be the number of non-trivial births at or and the number of non-trivial deaths at (and similarly for H). The O-dimensional PH of the filtration may be computed inductively by the following procedure.
For time after -oo to co. initialize the list with Bo (ooo)) tuples of the form (co, -). Each tuple represents a connected component Xy, where Xx 's and Yj are the connected components of Gao and Hog respectively. Then mark the remaining tuples as trivial holes, ie. (00, 0o).
For time after 04 as+1, i 120 0:
1. If Harp1 Ha., then there are exactly ( (G) non-trivial births of tuples of the form (d)+1.-). The non-trivial deaths that die al di+1 are exactly as follows- for each component Yj of Has and for each component X5 of Gay the component (Xix Y,) dies for all Xx 's that die in the filtration Go, C Gaay"
2. If Jaa+ Go; then a similar statement holds by symmetry.
3. In the general case, we refine the filtration of GUH from a; to ai+1 into a two-step filtration:
(B) Ho. C GamnDHo C DHa
(A)
and apply Step I to (A) and Step 2 to (B).
Note that when applying Step 2 to (B), "some of the non-trivial deaths produced are trivial deaths". The reason why is, although in algorithmic times, there may be vertices that are born in Ge. DH, and die in Ga; 1 Steps (A) and (B) both happened at the same time during filtration time.
Thus, we need to retroactively go back and mark all vertices born in Gaman Hay and die in Gaszg D trivial pairs. In total, this incurs a subtraction of be43 dG) ( (H) (where b is the number of non-trivial births from Go, C Gayp and 1 (H) is the number of non-irivial deaths from Ha; C Hagpyh ). with clear vertex representatives, from the components produced to be counted as trivial holds.
4. The remaining tuples produced but not in the discussion above are all trivial holes.
Proof of Theorem 6. For two arbitrary simple graphs A and B, we first observe note that 30 (ADB) (o(A))((B) This can either be seen directly from the definition or by noting that ACB is exactly the 1-skeleton of the topological product A x B (equipped with the canonical cell structure). Since removing 2-cells does not change connectivity, it follows that (ALBB M Ho(A x B), and the rank of the latter can be computed by the Kunneth formula to be (A) B). (Note that we are able to use the Kunneth formula here because the integral homologies of a (finite) graph are all finitely generated free abelian groups, so the rank does not change when switching to field).
Let us prove the theorem by induction. Our inductive hypothesis will be that the k-th step of the algorithm agrees with the PH diagram at the stage Go,, D...- Also note that Step 3 subsumes Step 1 and 2 special cases, so in our proof we only need to check Step 3 and 4. By convention, write a-1 -o. When k = -1, clearly this holds since the lists are both empty. At k = 0, the discussion in the paragraph above shows that it agrees with the PH diagram calculation.
Now by induction suppose we have that the result matches with PH up to i = i 2 O, then we wish to show this is also the case for k- = i + 1. By the algorithm, this step of the filtration is divided into
(B) GH,DHa, C Gaa,nDHa. C
Observe that this refinement clearly does not change the PH diagram (since the PH diagram is independent of the over of attaching new vertices and edges in one step of the baser-based filtration). Thus, we only need to show that the algorithm the Theorem provides behaves the same PH in both step (A) and (B).
Let us first examine (A). Now observe that Bo ac. DH..) (G,
= (Bu(Geus))
Bo(G.,)) Ha,) = (b:+1 d ( ()))) Hay). On the other hand, we also have that d (GDH). Thus, if we could show that it also follows that be+1 (GDH) = (G)) (H..) (which proves the birth times). Since there are already b, (G)) components created in the filtration
Bo(Ga, DH,,) - Bo, aH,.) = 1 (GDH)
(G H) = (G)
17

---

step (A) by the product, this would show that this constitutes all the non-triee non-trivial births (in particular this allows an identification of the component with the birth time).
Thus it suffices for us to show that the deaths occur exactly in the following form - for each component Y, of Hag and for each component Xx of Ga., the component (Xx; Y3) dies for all X 's that die in the filtration Go, C Gatt1. Now because the component from H does not change in this step, it is clear that there are least di+1(G) (G) (Ha;) such many deaths coming from the description above. What we want to check is that these are the only deaths that occur. Since we accounted for all possible merging of (Xk1, Y,) and (Xxg. Yj), another death that could occur has be of the form to merge (X&, ,, and (Xx, 122) (by the virtue of box product). However, for such death to occur, it must mean that has changed in the filtration, which is contradiction. Thus, we have identified all the deaths in the filtration step (A).
The case for (B) follows by symmetry, and gave extensive discussion in the theorem statement on why some non-trivial deaths would be marked as trivial deaths. Finally, by induction, we have proven the theorem.
Equivalence between Algorithm 1 and Algorithm 3: It suffices to show that the list nt _t_ births produced for both Algorithm and Algorithm 3 are the same. Indeed, at index i, nt_ birthh produced by Algorithm is exactly the set {(v, w) E GOH ((1) or (2)) and ((3) or (4))}, where:
(1) e is born non-trivially at a; and w is still alive a,-1-
(2) v is still alive at a, and w is born non-trivially a,
33) v is still alive at a,-1 and w is born non-trivially at a,
(4) v is born non-trivially at a and w is still alive at a,
On the other hand, the list ni birbis produces for Algorithm is exactly the set ((,w))
GDH (f)), where:
* (f) is the condition that (1) or (2) holds, but excluding the pairs (v, w) where is born non-trivially at a, and w dies a;-
Now suppose (v, w) is in nt_ births for Algorithm so (1) or (2) holds. Suppose for contradiction e is born non-trivially at ag and w dies at ag then the pair (v, w) is false for the statement (3) or (4), since both (3) and (4) require w to still be alive at a,. Thus, (v, w) in nt births for Algorithm
Now suppose (v, w) is in nt births for Algorithm 1, so (1) or (2) holds. We wish to show that (v, w) also satisfies (3) or (4). Indeed, since (v, w) is not excluded, this means that either (5) u is not born non-trivially a; (6) does not die ag In this case, see that:
If (1) holds, then (5) is not possible. (6) has to hold, which implies (4) holds.
If (2) holds, then (6) always holds, and is born non-trivially a; If is born before a;, then (3) holds. If is born at a,, is a non-trivial birth by (2) and (4) holds since w still alive at 0;.
For Runtime: We can compute the two individual persistence diagrams in O(me log(mc) + nG) and O(m log(m=) + ah) time. We can pre-compute the relevant data from the diagrams. If we assume the coloring set has constant size, then filtration steps also constant, so this can be done in the runtime dominated by the result of the theorem. We initialize the persistence diagram with nngh tuples with empty entries. In this case, when loop through the filtration steps, our (possibly unoptimized) algorithm implements the intermediate steps in the Theorem by looping through the non tuples. This yields the runtime as 0 mg log me mn log m nG + nH)) O
Now we will look of the algorithm for the product of two edge-level filtrations. Let us first rewrite the algorithmic description in Algorithm 2 into more mathematical formulation below.
18

---

Algorithm 3 Computing the O-dim PH Diagrams in Product of Vertex-Level Filtrations (Symmetric)
Input: The vertex-level filtrations (G, fG) and (H, fH)
Output: The 0-dim PH diagram for GGDH,fofi
1: imple. implæ <- O-dim PH diagrams for (G, JG) and (H, JH).
2: filtrationssteet + { filtration steps for fc and fи Uf+oo), and ordered.
3: birthsc, births f- list of tuples born non-trivially in G (resp. H) at each time in filtration_sted steps.
4: bettig. betti < list of vertices alive representing components of the subgraph of G (resp. H) each time filtration_steee
5: deathsg, deaths +- list of tuples that die non-trivially in G (resp. H) each time in filtration_stepr
6: Remove (-oo} from filtration_stan steps.
7: output < [(v, [ None) for (1,5) in V(G) x V(H).
8: for in [0, len(filtration_seess) do
9: a, < -fitrration_seeppe
for in deaths + do
Marking Non-Trivial Deaths
11:
Mark all tuples in output with p|1] = u,p < 0,, P[3 = None with p[3] + Aj.
12:
for in deaths + do
Marking Non-Trivial Deaths
13:
Mark all tuples in output with p|0] = w. p|2] < a;, P(3] = None with p(3] < 0g
14:
ni. mi_birthsl births + x bettin [i] + bettiali (i + 1] x births f ++1
nt mi_births22 + bettig x births (i + 1] birthsg (i + 1] x bettig 11.
16:
nt births +- nt birthsl nnt martht22t
17:
Mark all tuples p in output with (p(0).p(1]) & nt bu_births, p|2] = og p..p3]] Marking Trivial Deaths
None with
p[3] a,,
18:
return [(p[2), p(3]) for p output]
In the set-up of Proposition 7, mark all the time G,UHH, changes as ag a1 < on. The O-dimensional persistence diagram of (GDHf); G,OHH, with respect to f can be computed by the following procedure:
Theorem 7.
1. All vertices are born at time O.
2. For for each filtration step Da, S Gea we refine the step as
(A) G.,DHa C Ga.zi (B)
Cam,,HHass
3. In Step (A), there are hy Setz deaths. Here hy is the number of vertices alive Ho, and dit are the number of vertices that die in the step Ga, C Gaa-r
4. In Step (B), there are R:41 h4+1 deaths. Here de is the number of vertices alive in Gayy and hy41 is the number of vertices that die in the step Ha; C "Hass
5. The remaining vertices after on all die co.
The runtime is O(max(ng log Ti + TH log nHH mg log ma + nG. mH log m + =2H)).
that Algorithm outlined in Theorem 5 is equivalent to the description of Theorem 7, Thus, it suffices for us to prove Theorem Before this, we first give a concrete example of using Theorem 7.
Evidently,
Example 2. Consider the setup of = given in Figure 4, and so ag = 0, aj = 1, = 2. Note that Go is the discrete graph with 2 red nodes and I blue node. G1 connects an edge between I red node and I blue node. G2 connects the last remaining edge.
We wish to compute the PH of the product of edge filtrations on GOH. At t = 0, all vertices are ) At
spawned, so there are pairs of tuples of the form (0, -). during this time. This number can be seen from the algorithu as
we see that 5 vertex deaths occur
(3) (1) (2) (1) 5. 16 ot +h 11
Thus, we mark of the 9 tuples as (0. At we see that 3 vertex deaths occur during this time. This can be computed from the algorithm as
h 22 9 h (2) (1) (1) (1)
19

---

Proof of Proposition 8. Since a cycle born in graph never dies, the I-dimensional persistence diagrams are always of the form (b(e), oo) where represents the edge that creates an independent cycle. To track the evolution of the I-dimensional persistence diagrams for the product of any Thus, we mark 3 of the remaining tuples as (0, For t > 2, there is I vertex left, so we mark the last tuple as (0, 0o).
rzed fa(red, blue)
G= H
t=0
t=1
t=
Figure 4: The product of the edge filtrations G H given by fe (red, = 2 fe (red, blue)
See Example 2 for how the algorithm in Theorem 5 is used to compute the PH of this filtration.
We now proceed with the proof.
Proof of Theorem 7. For Algorithm Output: Step (1) is obvious. By the well-definedness of PH, the number of deaths the filitration Go C - D is the sum deaths in the two step refinement given. Thus, it suffices for to verify Step (A) gives the correct number of deaths, since the case for Step (B) follows by symmetric argument.
For the ease of notations, let us write n = hg and m = L. We seek to show that the number of (A) deaths in the step Ga, DHa C Ga Da, nm.
Indeed, since the number of vertices still alive in Ho, corresponds to its number connected components, can write C1...., On the connected components of Ha, Now we have that,
G., = G 0 (
C2) = L Go. Go. DCg and G CHa = L Ga4. DCJ- 3=1
The number of vertices that dies in Step (A) additive under this disjoint union, it suffices for us to show that the number of vertices that die in the step Ga, DC, C Ga OC₁ is m. Now indeed, write D1, ..., ..., De the connected components of G.. The connected components D, and D3
merged in the step Ga, C Gaser if and only if the connected components D,0C, and D&DC; are merged. This proves the desired claim.
For Runtime: We that Algorithm 2 does not need compute the graph product and is dependent on the PH for G and PH for H separately. As we discussed the paragraph under Theorem 4, the runtime to precompute the PH diagrams for G' and Hl respectively are O(me log(mg) ne) and O (og(m))) n We can precompute the number of non-trivial deaths and number of vertices still alive O (n))))) and O(n log(n=)) time by sorting the two (0-dim) PH diagrams by death-times and count accordingly. Then we loop through both lists in parallel to compute the diagram (which in linear time). Thus, the runtime of Theorem 5 would be (max((g log(ng) log(n H), mg log(ma) + ng, my log(m + nH)))
Finally, we discuss the algorithm for the I-dimensional PH diagrams of product of filtrations.
filtration, it suffices for us track how the first Betti number changes. The number of tuples created the difference between successive 3,
Thus, suffices for us to verify the formula for 31 (AMB). The box product ACB is exactly the 1 I-skeleton of the topological product G x H, endowed with the canonical CW complex structure
20

---

from both A and B. The Euler characteristic of the product of two finite CW complexes is the product of their Euler characteristics, so we have that X(A B) x(A)x(B) (see Exercise 2.2.20 of [22]). On the other hand, since ADB BBBke is the 1-skeleton of A x B, we have that
x(ADB) - x(A x B) - #E(A)
On the other hand we have that
(AAD))) (ADB),
and hence we have that
(ADB)) #E(A)# (( x(A)x(B).
Since removing 2-cells do not affect the connectivity of the complex, have that (o(ALI = 3o x B) = (o))))((B), where the last equality follows from Kunneth's formula. This concludes the proof.
For Runtime: For G and H graphs, we see that the quantity 31 (GDH) can be expressed in terms of (I) the number edges, (2) the number connected components, and (3) the number of vertices of G and H respectively. To compute the 1-dim persistence diagram of product filtration, it suffices for us to keep track of how (I), (2), (3) changes over time. These can all be done a time dominated by Ommg log mg + nG + me log ma + nH) (ie. the time to compute the persistence diagrams on the two separate graphs).
B A Max Version of Persistent Homology
In this section, we discuss max version of persistent homology where the edge-level filtration function fo in PH is determined by the vertex-level filtration function fu. We will show that the edge-level PH of max PH can be computed directly from the vertex-level PH. More precisely, we reformulate the first part of Proposition more generally to the following proposition:
Proposition 9. Let fo be a vertex-level filtration
filtraatoonn on G. Consider an edge-level filtration fo on G with 1. (w) is constant for all w E V(G) and is less than the minimum of F. on V(G).
2. Few w') = max(fu(w)) fo(w() for all (w, w') E E(G).
The vertex death-times of fe are the same as the death-times of fe. Furthermore, if the edge-level filtration is given decision rule kill off the vertex that has higher value under fo (and we arbitrarily choose which vertex to kill off in tie), it may be chosen so that the same vertices die at the same time for both filtrations.
Proof. To show that the death-times of fe the same that of Su. it suffices to check that each time step I, the number of vertices that die on both filtrations (notationally we write (t) and (t)) are the same. Indeed, write the possible values of fo in order as a1 < ... < an. Outside of this list of values, we clearly have that (t) (t) 0.
At t = 01 the vertex level filtration creates G(a1) (see Section 3 to see the notation) and all the deaths can only happen in G(az). At the same time, observe that all the edges spawned time t t= 01 for edge level filtration happens only in the subgraph of (a(a)) and gives the full subgraph G(ai). Thus, we have that (ai) = Da(a)). Furthermore in the first step, we could clearly choose the same vertices to kill off for both filtrations.
Now suppose by induction we have that at = a5-1, the previous death times have been the same and that we have chosen the same vertices to kill off for both filtrations. Now at t a, the vertex level filtration creates UJ- Es (a,, a;), and the edge level filtration also adds all the edges in U (aja az). For our purposes, the vertex level filtration will first spawn all of G(a:) first (before adding the edges in Ea(aj, a;) for j < i), and the edge level filtration will first add in all of the edges G(a,) similarly. this case, clearly we can still choose the same vertices to kill off for
both filtrations by the inductive hypothesis. Doing this up to a, concludes the proof.
D
21

---

D
A
E
B
Figure 5: Graph G in Example 3.
The second part of Proposition can be more generally reformulated to the following statement. Proposition 10. Lel J be vertex-level filtration on G. Consider the same edge-level filtration fe given in Proposition 9. The cycle birth times of the vertex-level filtration are the same the cycle birth-times of the edge-level filtration.
Proof. This because the birth-time of the edges are the same in both the vertex-level filtration and the edge-level filtration. Since color-based PH is independent of the order in adding in the simplicies marked with the same color, we can add the edges in both filtrations in order such that a cycle occurs in the vertex-level filtration if and only if it occurs in the edge-level filtration. A similar proof as in the previous proposition shows that the creation of cycles would be the same.
C An Example Computing EC
Here give explicit example computing the EC diagram.
Example 3. Consider the graph G in Figure with fu (r(ed = fbbuue) = =2, Se(ed,, 1, fablue, blue) = 2, (red, blue) = 3. We have that
EC(G. = x(Gf)))
0, -1 and F) =
(G()))(((f.)) = 2, 1.
Proof Example 3. Consider the set-up in the example again, recall this gives graph G with (red) = 1, fo (blue) = 2, fe (red, red) = 1, feblue,, blue) 2, fe (red, blue) = 3. We wish to show that
BC(G,f) = xfG)), ).x' = 01 and EC(G, = ((GG))xG))) ((G))))))))))))))))))) = 2, 11
Now to compute JVV we observe that Gf" is the subgraph of G generated by red vertices (A, B, C), so is the cycle graph of 3-vertices. Thus, x(G(-) = When t reaches 2, we have that G/ = G, so the Euler characteristic is -1.
Now to compute FC we note that at t = 0, G is the discrete graph on 5 vertices. At
t 1, all the red edges added in, Gf is the disjoint union of 2 vertices and the cycle graph of 3-vertices. Thus, X(G = + 2 = At l = 2, a single blue edge is added between the two disjoint vertices, so x = x(G
1. At 3, two more edges are added and hence
x(Gf))= -1-2=11
D Expressivity of EC on Simplicial Complexes
Let K be simplicial complex of dimension n where each vertex is assigned a color in some coloring set X. The Euler characteristic of K is defined by
X(K)
1))* (simplicies in K of dimension i}.
2=0
Notation:
Let CI,..., Gj E be list distinct colors with S j. we define 5 (ci, 6s) as the number of j-simplices in K whose vertice's ' set of colors is {ci...., ct).
22

---

Under suitable extension of the definition of EC and max EC diagrams to simplicial complex, we can, in fact, characterize them completely in terms of the combinatorial data provided by S (c.....,.)) We will make these definitions precise and in partieular prove the following theorem.
Theorem 8. Let K, M be simplicial complexes of dimension n. The following are equivalent:
1. EC(K, fo.. fn) = EC(M, fo.... f.. for all possible fo..... .... fn. Here, each ft is an i-simplex coloring function, to be elaborated upon in Appendix
2. ECT (K, = ECTh (M, Jo) for all possible fo-
3. For all S S (c1, (s) (c for all distinct colors Ci, Cs with
isisj.
Note that Theorem is stronger formulation of Theorem 3 in the main text.
We first extend our definition of EC and ECTM to a simplicial complex of dimension n with a vertex coloring function e ((K) X.
Definition 8. Let K be simplicial complex of dimension with vertex color set X. For 0 < < define color value function f: 11 X Rxo as follows:
1. For any permutation a E Si+1, fi(o(T)) = fi(
2. For any ž. I[ X such that म and have the same coorlinates modulo order and multiplicity, fi(T) f((T). For example, if X {red, blue), f2(red, red, blue) = fz(blue, blue, red). The intuition is, sets (so we forget about order and multiplicity). {red, red, blue) is the same set as (blue, blue, red}.
We define the i-th simplex filtration function fo of K follows:
For all simplices a with dimension less than i, F((O)) =0
For all i-simplices with vertices vo..... Us, Fi(a) = f:(c(vo). c(w)).
For all simplices with dimension greater than i, F((o) max4-simple r Co fo(T).
Note that when K = G is a graph fo: J1, Fo, F1 agrees with our construction of fer Ser Fu, Fe.
Finally. for each and E R, we define
Kf. = (1-000
From here, we can construct the EC and max EC diagram on simplicial complexes as follows.
Definition 9. Let K be a simplicial complex of dimension n with simplex filtration functions fo. fi, ...y fn. The EC diagram EC(K, Jo, [o..... of K is composed of n lists EC(K, fi) for i= O,.,,,, n1 n++11 1. For each write of < < On, as the list of values Js can produce, (C(KKfd) is the list (x(
only given a vertex filtration function fo- We define the max EC diagram of K as EC" EC"((K,f fo) = EC(K, for 91, ....... In). Here gi(o) = mixpes co max,e Er fo(w;).
Suppose
One can check that the gi's defining max EC are consistent with the setup in Definition 8. As an immediate corollary of Theorem 8, we will see that EC and EC"" have the same expressive power on the level of simplicial complexes.
Theorem 9. EC and ECTh have the same expressive power.
Remark 2. The choice of Condition (2) in Definition 8 is intentional that Theorem would hold. The intuition is that Condition (2) corresponds to coloring the i-th simplex a, with vertices vo...., 1 h of K with the feature being the (U...... v.41} } that forgets about multiplicity and order. However, Theorem is not true if we modify Condition (2) such that we color a with the feature being the multi-set (c(vo),... c(U4+1)} remember multiplicity.
We will now prove Theorem 8. To do this, will first prove lemma.
23

---

Lemma 1. Let K and M be two simplicial complexes of dimension n, they have the same max EC diagram for all possible for then K and M have the same f-vector, meaning that their respective number of simplicies are the same at each dimension.
Proof. For this proof, let K' denote the subcomplex of K with all simplicies with dimension < i. By comparing any complete filtration, we will have that x(K) = x(M) (so x(k"-1) x(Mx-1)) Comnparing time ( = 0 for any induced i-simplex coloring filtration by an injective fo will give us that x(Kt) - x(M") for all 0, ..., n From here we can see that they have the same f-vector.
Now we will finally prove Theorem 8.
Proof of Theorem 8. Clearly (1) implies (2). To see that (3) implies (1), we first note that (3) implies K and M have the same f-vector, so the starting values of their Euler characteristics for any f; are always the same. For any change of the Euler characteristic time varies, we will be modifying the value by adding subtracting values of the form 8 (C1, ..., ci) S (C1( c.). Hence, their Euler characteristics will agree as time varies.
For (2) implies (3), we first note that Lemma implies K and M have the same f-vector. We will now prove the claim from backward induction
0, 1, 1,.., n. Indeed, when j = have that
1. We will induct on 1 < i S n.. For i = 1, we wish to show that (c)) = Si (c) for all e E C. Note that 5% (c1) is just the number of n-simplicies whose vertices all have color C1. Choose fo such that ci has the minimum value, then under the induced max n-simplex coloring filtration, we have that
(K )o(e))) x(M ))()))
Since K and M have the same f-vector by Lemma conclude that (c)) - 5% (ci).
2. Suppose this is true up to < Indeed, let cı, Ck+1 be k + distinct colors. Choose fo such that q₁ has the minimum value, 22 is the second smallest, and so on until CK+1. Under the induced max n-simplex coloring filtration, we have that
< n. We wish show this true for i 1.
(K In ()) = xMM (M fo(ce+1))
Subtracting their Fuler characteristics at the time step fo(ck), we have that
(-1)" Σ (a)
Σ (a). aEA
where A is the collection of subsets of (ci,..., Cc+1 } that contains Ck+1- Since the inductive hypothesis is true up to = k, we know that for all a A such that |a] I k. (k = Stn (a). Hence cancelling both sides gives
Σ a
(k
Σ (a)(
aEA.|a|>
Now, there is only one element in A with |a] > k. namely a = {Ci, Ck+1). Hence, we have proven this for the case i = k 1.
3. Thus, by induction, we have shown this for j = n.
Now we will induct down from wish to show this is true for j = k. Now we wish to show that St (c1,...,G) = S (ci,.., G)) for all distinct colors Ci,..., G and 1 < i < k. We will do this by an induction on
n. Indeed, suppose this is true up to 0 < j == k + 1 n, we
24

---

1. For i = 1, we wish to show that S (c1) S/M (c1). Indeed, choose fo such that ej has the minimum value. Then we have that
x(K fa(es)) - x(M fo(cs))
Since K and M have the same f-vector, cancelling that out gives us that
" s
St(())
t=k
É=
By our inductive hypotehsis on j. we know that Sk (c1) (M) for all E> k. hence subtracting them off gives us that 5% (c)) S% (c)).
2. Suppose this is true up to 1 S = k. We wish to show this is true for i = L 1. Indeed, let ci...., C++1 be l distinct colors. Choose fo such that e₁ has the minimum value, c2 is the second smallest, and so on until ce+1. Under the induced max k-simplex coloring filtration, we have that
X folce+1)) = X(M fo(cue)))
Since they have the same Euler characteristies at the time step fo(ce+1), we can cancel those terms out and obtain
ΣE ΣΣ (-10 (a).
aEAp=k
aEAp=k
Here A is the collection of all subsets of fcr.... C2+1 that contains the color c++1- Now by the inductive hypothesis j, we know that ST (a) S (a) for all p k, so can cancel the expressions and obtain
(-1)² Σ (a)
Σ S (a).
aEA
aEA
Now by the inductive hypothesis for we have that for all |a| < ll 1. (a). hence we have that
(-1)²
Σ =
Σ (a).
=
aEA.
aEA.Ja/>
There is only one subset of size + 1, namely (cI. Hence, we conclude that Sk (c...... C(+1) Sh (ci, 1)+
Thus, by the principle of induction, we have proven that (2) implies (3).
E
Implementation details
E.1
Datasets
With the exception of ZINC, all datasets originate from the TUDataset repository a comprehensive benchmark suite commonly employed for assessing graph kemel methods and GNNs. The datasets can be accessed at https: / ccrssrrrs. - gi thub io/ datasetsssss/saaaaaeaaeaaaaaas /tt/////ca/aaeeeeeeeeeeee/e datasets/. ZINC(12K)
corresponds to subset of the widely used ZINC-250K collection of chemical compounds [28], which is particularly suited for molecular property prediction [12].
BREC is a benchmark designed to evaluate the expressiveness of graph neural networks (GNNs). comprises 800 non-isomorphic graphs organized into 400 pairs, grouped into four categories: Basic, Regular, Extension, and CFI. The Basic category includes 60 pairs of --WL-nniisiinguihabble graphs, while the Regular category contains 140 pairs of regular graphs further divided into simple regular, strongly regular, Lxvertex-conditinn and distance-regular graphs. For detailed description of the remaining categories and graph constructions, we refer the reader to Wang and Zhang [49].
For completeness, we also considered minimal Cayley graphs. These datasets have been used to https://houseof http///hooooofeoeeeeeee graphs org/
assess the expressivity of graph models [2] and can be found https: meta- www.reetor/mmiimmaat mamiiallcayll........mm. cayley.
Table 4 reports summary statistics of the real-world datasets used in this paper.
25

---

Table 4: Statistics of the datasets.
Dataset
#graphs
#classes
Avg #nodes
Avg #edges
NCTI
4110
2
29.87
32.30
PROTEINS (full)
1113
2
39.06
72.82
DHRF
756
42.43
44.54
NC1109
4127
29.68
32.13
COX2
467
2
41.22
43.45
ZINC
12000
23.16
49.83
E.2 Expressivity experiments
For each collection minimal Cayley graphs with n nodes (denoted by c-n), we compute all possible pairwise combinations. The BREC benchmark provides pairs of non-isomorphic graphs for each type: basic, regular, and extension - for computational reasons, do report results for CFI graphs. For both benchmarks, accuracy is measured as the fraction of pairs of graphs that can be distinguished by their O-dim and 1 1-dim persistence diagrams.
For edge closeness, we obtain an edge-level filtration by computing node closeness centrality on the line graph of each input graph. Recall that the closeness centrality of node is the reciprocal of its average shortest-path distance to all other nodes in the graph. We compute this quantity using nx. closeness cotsseesss_cetrralieeeee from the NetworkX library [20].
We also consider the Jaccard index, defined for an edge (u, v) as
J(u, #N(w) (N(())
where ((u) denotes the set of neighbors of in the graph. We use J(u, u) as an edge-level filtration value, computed via nx. jaccarc jaccard__coefficient coefficient.
Finally, we employ the square clustering coefficient vertex-level filtration, which measures the fraction of possible squares (i.e., 4-cycles) incident to a vertex in the graph. We compute using nx. stuuur_ecuuueerrreeeeeee
Implementation note. For the sake of transparency, while preparing the final version of the manuscript, we found an error in earlier implementation of expressivity experiments that erroneously reported perfect accuracy for GProd. After fixing the bug, we observed that, with our initial (simple) filtration choices, GProd and standard PH mostly achieve on par performance. To better highlight the benefits of GProd, we revisited the experimental setup by considering stronger filtration functions and additional datasets (including minimal Cayley graphs). Importantly, the corrected results corroborate our overarching theme that considering PH on graph products contain richer information than the individual components. Further details are provided in the official github repo.
E.3
Runtime experiments
The runtime experiments were conducted on Google Colab and written in Python. This was done in the standard Python 3 Google Compute Engine backend without any subscription. For the experiments comparing Theorem 4 with gudhi and union-find, we applied a vertex- based degree filtration the pair of graphs G and H and compute the induced product filtration experiments comparing Theorrm 5, we applied an edge-based filtration that is a modified version of the Forman-Ries Ricci Curvature [44] for graphs. More precisely, for edge (u, w) G. we apply
GDH. For the
felu, w) #V(w) #NW(w) + 3# (N) (W((w) + 2#V(G),
where #.(o) is the number of adjacent nodes and #V(G) is the number of nodes the entire graph. This is just done ensure
E.4 Experiments graph classification
We implement all models using the PyTorch Geometrie Library [17]. For all experiments, we use Tesla V100 GPU cards and consider memory budget of 64GB of RAM.
26

---

For the TU datasets, we use random 80/10/10% (train/validatiionnees) split, which varies with the ran- dom seed (i.e., different split used for each of the five runs). All models are trained with an initial learning rate of 10-3, which is halved if the validation accuracy does not improve for 10 consecutive epochs. We employ early stopping with patience of 40 epochs and train for up to 500 epochs using the Adam optimizer [31]. A batch size of 64 and batch normalization are used in all experiments.
We apply the vectorization scheme of [8] with Gaussian point transformations, identity weight function, and mean aggregation. Formally, let D {PI..... .PoJ be a persistence diagram with n tuples p; I.2. We compute
h(D)
Σ pp;)), n2 1=1
1
where
(()) = [,((,,) with rp(0:) exp (-ll::
| pl
(2)
and .1,..., 0 2 are learnable parameters. In all experiments, restrict our analysis to 0- dimensional persistence diagrams and adopt 100. Two filtration functions are considered: degree centrality and betweenness centrality. The optimal is determined, together with the number of GNN layers, based on validation performance - i.e., the filtration function is hyperparameter.
Here, the topological embeddings h(-) are concatenated with the graph-level GNN embeddings (obtained via a mean readout) and passed through an MLP consisting of two hidden layers with ReLU activations and hidden dimension of 64.
We consider seven graphs as references in our approach, implemented in the NetworkX library: wwr.sttrrrraphh nx wt..lollppppraape (3,3), nx. wawttattssttte strrrssssttogat.gapcccccc (10,2,0, 2), and nx. house_graph.
nx. www.ccyclllpppll (4), nx. star ggaaph nx. turan_graph (5,2), nx. complete_graph (5),
27

---

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

---

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

---

Answer: [Yes]
Justification: We provide link to the official repo in the Abstract. Also, all datasets are publicly available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (uttps://nips.. ec/
Policy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nips... public/guider "CodeSubmisss sssissiin wwsisssssiiiiyyyyocc for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Details on datasets, splits, and hyperparameters provided in Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We provide error bars for all experiments on real-world datasets.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
30

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We report the compute resources in Appendix E, including GPU cards used. We also report the running time of different algorithms Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /tt////eerss/////// cwtpurip..ccppull/// Setpulicc/tthcsuuiiiiii
Answer: [Yes]
Justification:
The authors have reviewed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification; We discuss the broader impacts the end of the main text (before the acknow]- edgments and references).
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
31

---

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

---

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

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https : httpa/rrps..cc/ooteeeeeeeeeeeeee / for what should or should be described.
34


Reviews:
[{"review_id": "3LnyWjJX9l", "reviewer": "Reviewer_MD6t", "summary": "This submission provides a theoretical analysis of different topological descriptors, i.e., Euler characteristics (EC) and persistent homology (PH). Based on the definition of the EC diagram and max EC diagram for EC, and box product for graph product, it analyzes the expressiveness power of EC and PH and show that PH gains strictly more information on graph products than the individual components. Two algorithms are provided for computing PH diagrams by focusing on the product of vertex-level and edge-level filtrations.", "questions": "1. What is the possible application of the proposed TDs, can you provide some experimental results for verification?\n2. Can we use the proposed descriptors to improve the traditional GNN expressiveness? Or how to use them for practical tasks?\n3. Besides the expressiveness, do we need to consider other metrics and aspects to assess / evaluate the topological descriptors? if yes, how about the results on them for the proposed EC and PH descriptors?\n4. The author discuss the persistent descriptors of a graph, what is the counterpart? Nonpersistent? what is the advantage of considering the persistent TD rather than the others?", "limitations": "None", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n   - The paper focuses on the theoretical treatment of topological descriptors based on the color-based filtration and provides rigorous proofs and clear characterizations of their properties from the expressiveness perspective; it also provides algorithm frameworks for computing the PH diagrams.\n\nWeakness:\n   - The definition and theoretical formulation are dense, the provided example are not sufficiently explained, which may cause some difficulty for following for people without similar background.\n   - There is no applications for the provided TD and experimental verification for the expressiveness power of defined diagrams and proposed algorithms, which also make the practical value of the proposed TD and algorithms unclear.\n   - It only focuses on the color-based filtration on graph and lacks comprehensive comparison with other types of filtrations and expressiveness aspects;  the analysis of the proposed algorithms in Theorem 4 and 5 are insufficient, e.g., computation complexity and computational cost.", "was_revised": true, "final_justification": "Most of my concerns are addressed based on the response provided by the author. However, the clarification and concise of the paper, especially the W1, should be taken seriously and hope they can be improved.", "rebuttal": "Thank you for your review - we reply below.\n\n```\n... theoretical formulation are dense, ... may cause some difficulty for following for people without similar background.\n```\nThanks for pointing this out. We will revise the background section to add more clarity. We can also expand more on additional background in the appendix if you think it would be good. In part to aid the ease of understanding for people who come from a less theoretical background, we have now implemented both **Theorem 4 and 5** in executable Python codes with experiments around them. Seeing the actual code should be much more parseable, and we will also adjust the descriptions in the theorems to look more like pseudocodes.\n\n```\nThere is no applications for the provided TD and experimental verification for the expressiveness power of defined diagrams and proposed algorithms, which also make the practical value of the proposed TD and algorithms unclear. [...] can you provide some experimental results for verification?\n```\nThanks for your comment. We evaluate expressivity using the BREC datasets~\\cite{brec}. \n\nGiven a pair of graphs $G$ and $H$, we apply persistent homology (PH) \non graph products to decide graph isomorphism as follows:\n\n  1. Compute the persistence diagrams for $G \\Box G$ and $G \\Box H$. \n    If the diagrams differ, we conclude that $G$ and $H$ are \n    **not isomorphic**. Otherwise, proceed to Step~2.\n\n  2. Compute the persistence diagrams for $G \\Box G$ and $H \\Box H$. \n    If these diagrams differ, we again conclude that $G$ and $H$ are \n    not isomorphic. If they are identical, the test is deemed \n    inconclusive (i.e., $G$ and $H$ are considered isomorphic by this test).\n\nFollowing this strategy, we compare our method (GraphProd) against PH (with vertex and edge filtrations) and RePHINE, considering several filtration functions: degree, betweenness centrality, closeness centrality, and Forman–Ricci curvature. Remarkably, GraphProd distinguishes all graphs, including the challenging Distance Regular (DR) and strongly regular (STR) cases, where the other descriptors fail to differentiate any pair.\n\n| **Filtration**   | **Diagram**       | **Reg** | **Ext** | **Basic** | **DR** | **STR** |\n|------------------|-------------------|--------:|--------:|----------:|-------:|-------:|\n| **Degree**       | PH$^V$ |    0.00 |    0.07 |      0.03 |   0.00 |   0.00 |\n|                  | RePHINE           |    0.94 |    0.77 |      0.97 |   0.00 |   0.00 |\n|                  | GProd$^V$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n| **Betweenness**  | PH$^V$ |    0.96 |    0.82 |      0.95 |   0.00 |   0.00 |\n|                  | RePHINE           |    0.98 |    0.94 |      1.00 |   0.00 |   0.00 |\n|                  | GProd$^V$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n| **Closeness**    | PH$^V$ |    0.26 |    0.46 |      0.27 |   0.00 |   0.00 |\n|                  | RePHINE           |    0.98 |    0.88 |      1.00 |   0.00 |   0.00 |\n|                  | GProd$^V$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n| **FR Curvature** | PH$^E$ |    0.94 |    0.70 |      0.97 |   0.00 |   0.00 |\n|                  | GProd$^E$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n\n[1] Towards Better Evaluation of GNN Expressiveness with BREC Dataset, ICLR 2024.\n\n[2] PersLay: A Neural Network Layer for Persistence Diagrams and New Graph Topological Signatures, AISTATS 2021.\n\n```\nIt only focuses on the color-based filtration on graph and lacks comprehensive comparison with other types of filtrations and expressiveness aspects; the analysis of the proposed algorithms in Theorem 4 and 5 are insufficient, e.g., computation complexity and computational cost.\n```\nPlease see the response above for experiments using filtraitons based on degree, betweeness, closeness, and FR curvature. We have implemented **Theorem 4** and **Theorem 5** in Python, their theoretical complexity and empirical runtime are discussed in more details in the response to **Reviewer quwk**.\n\nHere we summarize the main points.\n\n1. For **Theorem 5**, the runtime is $O(max(nG log(nG)+nH log(nH), mG log(mG) + nG, mH log(mH) + nH))$.\n\n2. Assuming the list of colors X is O(1), then for **Theorem 4**, the runtime is $ O(nG nH + mG log mG + mH log mH + nG + nH)$.\n\n3. We did empirical experiments to demonstrate the benefits of their run-times against two naive implementations - one computing the PH of the whole graph product using an union-find method for PH, and another computing the PH of the whole graph using the industry standard PH calculation function from gudhi. For both theorems, when the size of the graph scales up, they perform significantly better than the two naive methods.\n\n4. The following two tables report the average runtime (in seconds, taken over 10 trials) each algorithm took to go over the entire dataset (taken from BREC).\n\n | **Method**       | **Basic**|**STR** | **DR** | **CFI**|\n|-------------------|--------|--------|----------|-------|\n| Theorem 4 (ours) | **0.967** |**2.040**|  **1.554** | **31.253** |\n| Naive PD | 1.427  | 33.691  |  22.569 | 673.253 |\n| gudhi  |  1.091  |16.469| 10.243 | 106.463 | \n\n| **Method**       | **Basic**|**STR** | **DR** | **CFI**|\n|-------------------|--------|--------|----------|-------|\n| Theorem 5 (ours) | 0.859 | **1.527** | **1.055**  |**5.899**|\n| Naive PD | 1.465  |38.828| 24.138 |742.611|\n| gudhi  | **0.065**|4.110| 2.179 |32.111| \n\n```\nCan we use the proposed descriptors to improve the traditional GNN expressiveness? Or how to use them for practical tasks?\n```\nThanks to your question, we run experiments for graph classification on real-world data to demonstrate how the proposed descriptors can be used to boost the performance of GNNs. For this, we employ the following procedure:\n\n1. **Define a family of small reference graphs**. We selected eight graphs generated using the NetworkX library: nx.cycle_graph(4),nx.complete_graph(5),nx.star_graph(5), nx.lollipop_graph(3,3),nx.watts_strogatz_graph(10,2,0.2),nx.turan_graph(5,2), nx.house_graph();\n\n2. **Compute pairwise product filtrations**. For an incoming graph G, we compute the product filtration (using betweenness centrality as filtration function) between G and each reference graph. This will result in 8 persistence diagrams.\n\n3. **Vectorize the diagrams**. We vectorize the obtained diagrams from previous step using any suitable scheme (e.g., DeepSets or the methods in [2]). In this work, we applied Gaussian vectorization [2] with q=10\n\n4. **Merge topological and GNN embeddings**. We concatenate the topological embeddings with GNNs embeddings before sending it through a classification head.\n\nWe considered 2 GNN models: GIN and GraphSAGE with either 2, 3 or 4 layers (selected via validation set). We assessed the models in 4 real-world datasets: NCI1, NCI109, ZINC, and PROTEINS. Here are the results:\n\n| Model                   | PROTEINS   | NCI1      | NCI109    | ZINC      |\n|-------------------------|------------|-----------|-----------|-----------|\n| **GIN**                 | 68.75 ± 1.55 | 80.62 ± 0.37 | 76.67 ± 1.61 | 0.58 ± 0.01 |\n| **GIN + ProdFiltration**| 69.05 ± 2.25 | 81.43 ± 0.51 | 77.72 ± 1.37 | 0.58 ± 0.01 |\n| **SAGE**                | 69.35 ± 2.25 | 77.62 ± 3.05 | 77.80 ± 1.38 | 0.54 ± 0.01 |\n| **SAGE + ProdFiltration**| 70.24 ± 2.87 | 78.02 ± 2.03 | 78.29 ± 1.46 | 0.52 ± 0.01 |\n \nAs we can see, the topological descriptors lead to boost across most combinations of GNNs and datasets. Overall, this illustrates the practical relevance of our contribution.\n\n\n```\nDo we need to consider other metrics and aspects to assess / evaluate the topological descriptors? if yes, how about the results on them for the proposed EC and PH descriptors?\n```\nComputational costs and scalability are also important metrics. Please see our response to the third weakness above for more details on how they interact with PH. EC itself is much simpler and faster to compute due to being less expressive. \n\nWe also made an implementation of **EC** and **max EC** in Python. To run a small experiment, we took the first 10 pairs of graph from basic.npy in the BREC dataset and used **EC** and **max EC** to run expressivity tests. For each pair of graphs G and H, we pre-assign them with vertex colors using the degree function. We then iterate through the list of possible color-based filtrations until the two diagrams either differ or we exhaust the list.\n\nIn a single pass, **max EC** finished the tests in 0.311 seconds. **EC** finished the tests in 69.624 seconds. The reason why is because of **Theorem 1** - for **max EC**, we only need to look at a sub-collection of **max-induced filtration** to get the same power, so the code only needed to only go through that sub-collection for **max EC**\n\n```\nThe author discuss the persistent descriptors of a graph, what is the counterpart? Nonpersistent? what is the advantage of considering the persistent TD rather than the others?\n```\nThe counterpart would be a **static** descriptor. A **persistent** descriptor for a graph is a method that involves some computations with respect to a filtration of the graph. Persistent homology, for example, looks at how connected components and cycles are born and killed in a given filtration of a graph, so these descriptors typically track an evolution of some information over time. A static descriptor does not look at a filtration, it only looks like the graph in its final state and produces some output. For example, the number of connected components and cycles of the whole graph G is a static descriptor, whereas reporting how these two information changes over time would be a persistent descriptor. One reason why persistent descriptors may be more preferable than static ones is because it is often more expressive. This is because the static one only looks at what happens at the very end, whereas persistent looks at what happens in the filtration of the graph."}, {"review_id": "UaMZ2PWWox", "reviewer": "Reviewer_Ytkj", "summary": "This paper analyzes topological descriptors (persistent homology (PH) and Euler characteristic (EC)) and their behavior when lifting to (Cartesian) graph products, providing a thorough theoretical framework for understanding their behavior under color-based filtrations.\n\nKey contributions include:\n\n- The introduction of max PH and max EC diagrams, with proofs of bijections between vertex and edge-level filtrations.\n- A complete characterization of EC expressivity for graphs with color filtrations, showing EC and its proposed “max” variant are equally expressive yet the max version is more computationally efficient.\n- A formal study of **graph products**, demonstrating that while EC gains no new expressivity on products, PH of product graphs (with  the addition of “virtual” nodes) is strictly more expressive than for components alone.\n- Algorithms to compute **0- and 1-dimensional persistence diagrams** for product filtrations derived from vertex- and edge-level colorings, showing how the product filtration can be decomposed into simpler component filtrations.", "questions": "1. Can you more clearly motivate why product graphs matter for ML tasks? E.g., subgraph GNN architectures, relational data modeling—concrete scenarios or prior work where your theory would plug in? Here I think elaborating in particular on the connection to relational databases modeling via GNNs and how this relates to product graphs could take a front seat in the introduction. I think EC and PH are well-studied and motivated, but the need for the calculus and understanding these descriptors when lifting to products would be better placed here than in Section 4.\n2. Could you separate out and clarify the definition of the **max-induced edge coloring function**? Currently it's embedded in the EC diagram definition and I think it might be more clear (including in the reference in Prop 1) if this got its own definition and explanation and set up the motivation for why this produces the \"max EC diagram\" and collapses the need to deal with both vertex and edge coloring functions.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n\n- **Technical depth and rigor:** The paper presents formal, well-structured theorems (e.g., Theorem 2's equivalence between EC and max EC) with detailed, convincing proofs.\n\n- **Novelty:** The approach to EC expressivity via vertex-based filtrations and their “max” counterpart for edge-based filtrations offers a compelling unification, highlighting an instructive example where PH achieves greater expressivity than EC—an interesting trade-off given EC’s computational efficiency.\n\n- **Potential impact:** By formalizing product filtrations and developing a clear calculus for them, the paper provides a solid foundation for improved topological descriptors on graph products. This framework can exploit decomposition properties and clarifies contexts where PH’s expressivity has clear advantages over EC.\n\n**Weaknesses:**\n\n- **Motivation for ML community is underdeveloped:** While the paper mentions subgraph GNNs and multi-way data, the introduction lacks concrete use cases or experiments demonstrating practical relevance. For example, the connection to relational databases (Robinson et al.) is super interesting and could be motivated further to captivate a more general audience.\n- **Justification:** Solid theoretical contribution with meaningful advances in understanding topological descriptors on graph products. It's a borderline accept because its practical ML motivation needs strengthening. I'd be open to raising my score if the authors clarified motivation and improved exposition.", "was_revised": true, "final_justification": "The updated experiments and improved motivation significantly strengthen the paper’s impact and clarity, addressing key concerns and justifying my increased score.", "rebuttal": "We are grateful for your time and comments. We reply to your comments/questions below.\n\n```\nMotivation for ML community is underdeveloped: While the paper mentions subgraph GNNs and multi-way data, the introduction lacks concrete use cases or experiments demonstrating practical relevance.\n```\nThanks for your comment. We conducted two sets of experiments to demonstrate the practical relevance of our paper.  \nFirst, we consider expressivity tests using the BREC benchmark [1]. In this regard, we show that Graph Products allow distinguishing all pairs of non-isomorphic graphs in BREC, surpassing previous topological descriptors (e.g., RePHINE). The results (accuracy) are: \n\n\n| **Filtration**   | **Diagram**       | **Reg** | **Ext** | **Basic** | **DR** | **STR** |\n|------------------|-------------------|--------:|--------:|----------:|-------:|-------:|\n| **Degree**       | PH$^V$ |    0.00 |    0.07 |      0.03 |   0.00 |   0.00 |\n|                  | RePHINE           |    0.94 |    0.77 |      0.97 |   0.00 |   0.00 |\n|                  | GProd$^V$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n| **Betweenness**  | PH$^V$ |    0.96 |    0.82 |      0.95 |   0.00 |   0.00 |\n|                  | RePHINE           |    0.98 |    0.94 |      1.00 |   0.00 |   0.00 |\n|                  | GProd$^V$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n| **Closeness**    | PH$^V$ |    0.26 |    0.46 |      0.27 |   0.00 |   0.00 |\n|                  | RePHINE           |    0.98 |    0.88 |      1.00 |   0.00 |   0.00 |\n|                  | GProd$^V$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n| **FR Curvature** | PH$^E$ |    0.94 |    0.70 |      0.97 |   0.00 |   0.00 |\n|                  | GProd$^E$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n\n\n\nIn addition, we demonstrate how the proposed descriptors can be combined with GNNs to improve predictive performance on four graph-classification datasets. Our strategy is as follows:\n\n1. **Define a family of small reference graphs**. We selected eight graphs generated using the NetworkX library: nx.cycle_graph(4), nx.complete_graph(5), nx.star_graph(5), nx.lollipop_graph(3,3), nx.watts_strogatz_graph(10,2,0.2), nx.turan_graph(5,2), nx.house_graph();\n\n2. **Compute pairwise product filtrations**. For an incoming graph G, we compute the product filtration (using betweenness centrality as filtration function) between G and each reference graph. This will result in 8 persistence diagrams.\n\n3. **Vectorize the diagrams**. We vectorize the obtained diagrams from previous step using any suitable scheme (e.g., DeepSets or the methods in [2]). In this work, we applied Gaussian vectorization [2] with q=10\n\n4. **Merge topological and GNN embeddings**. We concatenate the topological embeddings with GNNs embeddings before sending it through a classification head.\n\nWe consider GINs (graph isomorphism networks) and GraphSAGE. The results are:\n\n| Model                   | PROTEINS   | NCI1      | NCI109    | ZINC      |\n|-------------------------|------------|-----------|-----------|-----------|\n| **GIN**                 | 68.75 ± 1.55 | 80.62 ± 0.37 | 76.67 ± 1.61 | 0.58 ± 0.01 |\n| **GIN + ProdFiltration**| 69.05 ± 2.25 | 81.43 ± 0.51 | 77.72 ± 1.37 | 0.58 ± 0.01 |\n| **SAGE**                | 69.35 ± 2.25 | 77.62 ± 3.05 | 77.80 ± 1.38 | 0.54 ± 0.01 |\n| **SAGE + ProdFiltration**| 70.24 ± 2.87 | 78.02 ± 2.03 | 78.29 ± 1.46 | 0.52 ± 0.01 |\n\nAs we can see, the topological descriptors consistently yield improvements across most GNN–dataset combinations, underscoring the practical significance of our contribution.\n\n[1] Towards Better Evaluation of GNN Expressiveness with BREC Dataset, ICLR 2024.\n\n[2] PersLay: A Neural Network Layer for Persistence Diagrams and New Graph Topological Signatures, AISTATS 2021.\n\n```\nJustification: Solid theoretical contribution with meaningful advances in understanding topological descriptors on graph products. It's a borderline accept because its practical ML motivation needs strengthening. I'd be open to raising my score if the authors clarified motivation and improved exposition.\n...\nCan you more clearly motivate why product graphs matter for ML tasks? E.g., subgraph GNN architectures, relational data modeling—concrete scenarios or prior work where your theory would plug in? Here I think elaborating in particular on the connection to relational databases modeling via GNNs and how this relates to product graphs could take a front seat in the introduction. I think EC and PH are well-studied and motivated, but the need for the calculus and understanding these descriptors when lifting to products would be better placed here than in Section 4.\n```\nThank you for raising this question! Here, we elaborate on why graph products show up in terms of relational databases.\n\nRecall that for vertices (g1, h1), (g2, h2) in G \\Box H, we say there is an edge between them if either (g1 = g2 ^ h1 ~ h2 in H) or (g1 ~ g2 in G and h1 = h2).\n\nSuppose for example you have two tables - Table A is the wage income of residents in New York, and Table B is the wage income of residents in London, with some additional demographic / financial information for both. For each table, we view the rows as nodes. Now assign a similarity metric on the rows (ex. we are grouping people with similar income and background together), such that two nodes with sufficient similarity are linked with an edge.\n\nNow suppose your goal is to compare the residents in New York vs the residents in London based on this, then one natural operation would be to take the Cartesian product of the tables, call this new table \"Table C\". A reasonable graph one can make out of Table C is as follows - the nodes are still the rows. Let us think about how edges should be made. For person X in Table A paired with person Y in Table B, in order to analyze how X compares with Y and those similar to Y, we ought to look at how X connects with everyone in Table B that are connected to Y under the similarity metric before. What this means in terms of graphs is that we should link the node (X, Y) to (X, Y') for all Y' that is linked to Y. We can also do this symmetrically, and we can see that the construction of a graph under this heuristics is exactly the graph (box) product of Table A and B.\n\nThus, we see that graph products show up naturally in the context of relational databases, and we will expand on this in the introduction.\n\nWe now also provide experimental evidence to illustrate the merits of filtrations on graph products in terms of expressivity benefits. Furthermore, such filtrations can also be used for performing graph classification. Please see the responses above for further details.tails.\n\n```\nCould you separate out and clarify the definition of the max-induced edge coloring function? Currently it's embedded in the EC diagram definition and I think it might be more clear (including in the reference in Prop 1) if this got its own definition and explanation and set up the motivation for why this produces the \"max EC diagram\" and collapses the need to deal with both vertex and edge coloring functions.\n```\nThank you for the question. To clarify, a color-based filtration in Def 1 requires a pair of functions fv and fe. In a max-induced filtration, the function fe is dependent on the function fv. In particular, for an edge (a, b), fe(a, b) := max(fv(a), fv(b)) (ie. it takes the value of the vertex with greater value under fv). By a max-induced filtration, we mean color-based filtration in Def 1 with some fv and fe defined in terms of fv as above. max EC is the restriction of EC to only the max-induced filtrations. We will clarify this in the paper.\n\n**Additional Notes:** Also, we wanted to let you know that we analyzed the theoretical run times of **Theorem 4** and **Theorem 5** as well, and we did empirical experiments to demonstrate the benefits of their run-times against two naive implementations - one computing the PH of the whole graph product using an union-find method for PH, and another computing the PH of the whole graph using the industry standard PH calculation function from gudhi. For both theorems, when the size of the graph scales up, they perform significantly better than the two naive methods. \n\nThe following two tables report the average runtime (in seconds, taken over 10 trials) each algorithm took to go over the entire dataset (taken from BREC).\n\n | **Method**       | **Basic**|**STR** | **DR** | **CFI**|\n|-------------------|--------|--------|----------|-------|\n| Theorem 4 (ours) | **0.967** |**2.040**|  **1.554** | **31.253** |\n| Naive PD | 1.427  | 33.691  |  22.569 | 673.253 |\n| gudhi  |  1.091  |16.469| 10.243 | 106.463 | \n\n| **Method**       | **Basic**|**STR** | **DR** | **CFI**|\n|-------------------|--------|--------|----------|-------|\n| Theorem 5 (ours) | 0.859 | **1.527** | **1.055**  |**5.899**|\n| Naive PD | 1.465  |38.828| 24.138 |742.611|\n| gudhi  | **0.065**|4.110| 2.179 |32.111| \n\nPlease see more details in the response to **Reviewer quwK**.\n\n----\nMany thanks for your insightful review and constructive feedback. We hope your concerns have been satisfactorily addressed, and if so, would appreciate if you could revisit your score to reflect the same. We are also committed to engaging further if you have any additional questions, concerns, or suggestions."}, {"review_id": "quB3CK4cY9", "reviewer": "Reviewer_ETh2", "summary": "The authors establish a characterization of the expressivity of persistent homology (PH) and Euler Characteristic (EC) of the filtrations over graph products. The authors also establish a characterization of EC on general color-based filtrations. Further, they show that PH of graph products captures strictly more information than PH of single graphs while EC does not. They also give algorithms to compute the PH diagrams of vertex- and edge-level filtrations on the graph product.", "questions": "1. In line 65, shouldn’t it be $E \\subseteq V \\times V$, instead of $E \\subseteq V \\times X$?\n\n2. What is the larger picture of having defined coloring filtrations? One could have just started with two different filtration functions: first where one starts with a filtration function on the vertices and extends is piecewise linearly onto the edges, and another where all the vertices have zero filtration values and has some non-zero values on edges. I feel defining the coloring based filtrations, especially the way it is defined is rather confusing for the meaning it is conveying.\n\n3. Line 91-92: What do you mean by “filtration of a diagram”?\n\n4. The definition of $f_v$, seems to imply that one has a function $f_v$ for each vertex $v$. Moreover, since the function is not defined as $f_v : V \\to \\mathbb{R}$, but as $f_v : X \\to \\mathbb{R}$, it is understandable that each vertex has a potentially different function $f_v$. However, the writing seems to hint at the fact that $f_v$ is just one function that is defined as a filtration function on the vertices, which doesn’t seem right because the domain is not the set of vertices. Moreover, if it is so, then what is the point of the coloring function $c$? One could just consider $f_v \\circ c$ as a filtration function on the vertices which is the standard setting for PH?\n\n5. Moreover, it seems like this is an analysis of a bifiltration over a graph where $f_v$ and $f_e$ are two different filtrations.", "limitations": "Yes.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe paper is well-presented. I like the boxes around theorems.\n\nWeaknesses:\n\nThe choice of notation for $F_v$ seems slightly confusing. I think having the notation depending on $f_v$ makes more sense than $v$. $f_v$ makes sense because it is tied to a vertex $v$. However, $F_v$ is not tied to a vertex, rather it is tied to the function $f_v$.\n\nThe authors have motivated the need for graph products in a few lines towards the beginning of Section 4. However, the motivation seems lacking in concrete intuition and examples for the need of graph products. E.g., \"From an expressivity standpoint, graph products also capture information that the individual components may not have\", this line is vague and doesn't get across the idea that the authors are trying to convey.\n\nRefer to Questions.\n\nTypos:\n\nLine 65: “A graph is a the…” -> “A graph is the data…”?", "was_revised": true, "final_justification": "The authors have engaged extensively in discussions and have clarified the questions I had. I believe that this method can be useful for the Topological Machine Learning community and would recommend a borderline accept.", "rebuttal": "Thank you for your time and comments. We reply to your comments/questions below.\n\n### Motivation\n```\nThe authors have motivated the need for graph products in a few lines towards the beginning of Section 4. However, the motivation seems lacking in concrete intuition and examples for the need of graph products. E.g., \"From an expressivity standpoint, graph products also capture information that the individual components may not have\", this line is vague and doesn't get across the idea that the authors are trying to convey.\n```\nThank you for raising this question! Here we give 2 motivations for graph products - 1. they show up naturally in the context of relational databases and 2. they can perform quite well in expressivity tests.\n\n**Relational Databases**: \nRecall that for vertices (g1, h1), (g2, h2) in G \\Box H, we say there is an edge between them if either (g1 = g2 and h1 ~ h2 in H) or (g1 ~ g2 in G and h1 = h2).\n\nSuppose for example you have two tables - Table A is the wage income of residents in New York, and Table B is the wage income of residents in London, with some additional demographic / financial information for both. For each table, we view the rows as nodes. Now assign a similarity metric on the rows (ex. we are grouping people with similar income and background together), such that two nodes with sufficient similarity are linked with an edge.\n\nNow suppose your goal is to compare the residents in New York vs the residents in London based on this, then one natural operation would be to take the Cartesian product of the tables, call this new table \"Table C\". A reasonable graph one can make out of Table C is as follows - the nodes are still the rows. Let us think about how edges should be made. For person X in Table A paired with person Y in Table B, in order to analyze how X compares with Y and those similar to Y, we ought to look at how X connects with everyone in Table B that are connected to Y under the similarity metric before. What this means in terms of graphs is that we should link the node (X, Y) to (X, Y') for all Y' that is linked to Y. We can also do this symmetrically, and we can see that the construction of a graph under this heuristics is exactly the graph (box) product of Table A and B.\n\nThus, we see that graph products show up naturally in the context of relational databases, and we will expand on this in the introduction.\n\n**Expressivity Tests**: \nAnother motivation comes from that graph products appear to do quite well empirically in expressivity tests. We considered expressivity tests using the BREC benchmark [1]. In this regard, we show that Graph Products allow distinguishing all pairs of non-isomorphic graphs in BREC, surpassing previous topological descriptors (e.g., RePHINE [2]). The results (accuracy) are: \n\n\n| **Filtration**   | **Diagram**       | **Reg** | **Ext** | **Basic** | **DR** | **STR** |\n|------------------|-------------------|--------:|--------:|----------:|-------:|-------:|\n| **Degree**       | PH$^V$ |    0.00 |    0.07 |      0.03 |   0.00 |   0.00 |\n|                  | RePHINE           |    0.94 |    0.77 |      0.97 |   0.00 |   0.00 |\n|                  | GProd$^V$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n| **Betweenness**  | PH$^V$ |    0.96 |    0.82 |      0.95 |   0.00 |   0.00 |\n|                  | RePHINE           |    0.98 |    0.94 |      1.00 |   0.00 |   0.00 |\n|                  | GProd$^V$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n| **Closeness**    | PH$^V$ |    0.26 |    0.46 |      0.27 |   0.00 |   0.00 |\n|                  | RePHINE           |    0.98 |    0.88 |      1.00 |   0.00 |   0.00 |\n|                  | GProd$^V$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n| **FR Curvature** | PH$^E$ |    0.94 |    0.70 |      0.97 |   0.00 |   0.00 |\n|                  | GProd$^E$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n\n\n### Typos\n```\nLine 65: “A graph is a the…” -> “A graph is the data…”?\n```\nThanks for catching this. We will fix it in the revision.\n\n```\nIn line 65, shouldn’t it be E \\subset V x V, instead of E \\subset V x X\n```\nThanks for catching the typo. We will fix it in the revision.\n```\nLine 91-92: What do you mean by “filtration of a diagram”?\n```\nThanks for catching the typo, we meant **graph** instead of **diagram**. We will fix it in the revision.\n\n\n### Color Filtrations\n```\nThe choice of notation for Fv seems slightly confusing...\n\nWhat is the larger picture of having defined coloring filtrations? One could have just started with two different filtration functions: first where one starts with a filtration function on the vertices and extends is piecewise linearly onto the edges, and another where all the vertices have zero filtration values and has some non-zero values on edges. I feel defining the coloring based filtrations, especially the way it is defined is rather confusing for the meaning it is conveying.\n\nThe definition of f_v seems to imply ...  the writing seems to hint at the fact that $f_v$ is just one function that is defined as a filtration function on the vertices, which doesn’t seem right because the domain is not the set of vertices. \n```\nThank you for the comments. To clarify, the lower script v in $f_v$ does not represent a vertex v on a graph. As explained in Definition 1, $f_v$ is defined with respect to a color set $X$ rather than a specifc vertex. We will clarify this and change the notation $f_v$ to $f_{vx}$ and $f_e$ to $f_{ed}$ if you think that would help with the clarity.\n\n$(f_v, f_e)$ is defined with respect to a coloring set $X$. The benefit of defining them this way is that, for any graph $G$ with a coloring set $X$, we can use the pair $(f_v, f_e)$ to produce an induced filtration of $G$. This is very important in terms of expressivity tests. \n\nFor example, if we have two graphs $G, H$ with the same coloring set $X$. We want to use the PH of some filtration to determine if they are isomorphic or not. The issue is that, even if G and H are isomorphic, it is not in general true that a random filtration on G and a random filtration on H would give the same PH diagram. Therefore, randomly selecting filtrations on G and H respectively would not make a valid graph isomorphism test.\n\nTherefore, in order for the graph isomorphism test using PH to be well-defined, the filtration on $G$ and the filtration on $H$ must be dependent on one another in some way. This is to ensure that if G and H are isomorphic, the graph isomorphism tests here would not give false negatives. Now, since G and H have the same coloring set $X$, one way to find two filtrations that are related to each other is if they are both induced by the same pair $(f_v, f_e)$. In this case, the PH diagram would be an isomorphism invariant! (See [3])\n\nThis is why we defined $(f_v, f_e)$ (and consequently the color-based filtrations) so that the correspondent graph isomorphism test with the PH diagrams would be valid. To not confuse $f_v$ with the actual filtration defined on the graph $G$, we use $F_v$ to denote essentially $f_v \\circ c$ as in Definition 1.\n\n```\nwhat is the point of the coloring function c? One could just consider f_v o c ...\n```\nThe point of having the color function $c$ is because we want the color set $X$ to be intrinsically defined (it is supposed to represent attributes labeled to the graph) as opposed to being a subset of the real numbers. If we have considered $f_v \\circ c$ directly without passing through an intermediate $X$, this means that we are assigning real numbers as the attributes of the graph. However, often times the attributes of the graph may include non-numerical data. This is really a special case where the colr set $X$ is a subset of the real numbers. The purpose of having the function $c: V(G) \\to X$ is that it would retain the specific attributes that the graph would have without ``converting\" them into real numbers directly.\n\nWe do remark that, in practice, sometimes we would assign the color on the vertex as a real number directly and take $f_v$ to be the identity, such as when we did the expressivity tests. But note that we could totally modify $f_v$ to get other kinds of filtrations while keeping the same colors. \n\n```\nMoreover, it seems like this is an analysis of a bifiltration over a graph where fv and fe are two different filtrations.\n```\nThank you for the question. If by a **bifiltration**, you mean a **2-parameter** filtration, then the answer is no. In 2-parameter persistence, we define a function h: G -> R^2 (instead of h: G -> R). There is no time anymore, but rather a partial order on R^n. In our case, we can define a 2-parameter filtration of h: G -> R^2 as the collection G_{s,t} = h^{-1}( (-infty, s] x (-infty, t]) for (s,t) in R^2 (which also changes only finitely many times). The important observation to note is that there is now a matrix of graphs as opposed to a line of subgraphs in the 1-parameter case. This is different from looking at fv and fe separately in our case!\n\n---\nMany thanks for your insightful review and constructive feedback. We hope your concerns have been satisfactorily addressed, and if so, would appreciate if you could revisit your score to reflect the same. We are also committed to engaging further if you have any additional questions, concerns, or suggestions.\n\n[1] Towards Better Evaluation of GNN Expressiveness with BREC Dataset, ICLR 2024.\n\n[2] Immonen et al, Going beyond persistent homology using persistent homology.NeurIPS 2024.\n\n[3] On the Expressivity of Persistent Homology in Graph Learning. Ballester and Rieck."}, {"review_id": "NArKN42Iyn", "reviewer": "Reviewer_6YNL", "summary": "This paper investigates topological descriptors on graph products,  EC and PH. Specifically, the authors prove the expressive power of EC and PH on graph products and propose a PH computation algorithm tailored for filtrations on such structures.", "questions": "The authors could at least propose some preliminary experimental designs, which would significantly strengthen the paper. For example, one could verify that graph products enhance the expressive power of persistent homology (PH) on synthetic graphs [1]. Additionally, for a graph classification task, it would be valuable to compare the effectiveness of PH and Euler characteristic (EC) under the graph product structure, observing the performance improvements of classification models [2].\n\n[1] Ballester R, Rieck B. On the expressivity of persistent homology in graph learning[J]. arXiv preprint arXiv:2302.09826, 2023.\n\n[2] Zhao Q, Ye Z, Chen C, et al. Persistence enhanced graph neural network[C]//International Conference on Artificial Intelligence and Statistics. PMLR, 2020: 2896-2906.", "limitations": "The authors have already discussed the key limitations of their work.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. The study of topological data analysis methods on graph products is both novel and insightful. It has the potential to inspire future work in the machine learning community.\n\n**Weaknesses**\n\n1. As a submission to a machine learning conference, the absence of experiments is a major shortcoming. Although the authors emphasize the potential of PH in neural network applications, no experimental results are provided to support this claim.\n\n2. The lack of an experimental section also affects the overall structure of the paper. In particular, Section 3 feels disconnected and could be moved to the appendix to allow the main text to focus more clearly on topological descriptors for graph products. Accordingly, the introduction should also be revised to reflect this structural shift.", "was_revised": true, "final_justification": "I am pleased to see that the authors have added experiments and verified the effectiveness of their method. I believe the authors have proposed an interesting method that is also valuable to the community, and recommending the acceptance of this paper is a natural choice.", "rebuttal": "Thank you for your suggestions to strengthen our work.\n\n### Experiments\n```\nAs a submission to a machine learning conference, the absence of experiments is a major shortcoming. Although the authors emphasize the potential of PH in neural network applications, no experimental results are provided to support this claim.\n```\nThanks for your comment. As suggested, we have added three sets of experiments: \n1) expressivity on BREC datasets --- here, surprisingly, we found that simple filtration functions on Graph Products can distinguish all pairs of graphs on BREC. \n\n2) graph classification on NCI1, NCI109, PROTEINS, ZINC. Here, we showed that the topological descriptors consistently boost the performance of GNNs (SAGE, GIN).\n\n3) Experimental validations for the runtime benefits of the proposed algorithms in **Theorem 4** and **Theorem 5**.\n\nPlease, see the next answers for details and results. \n\n```\nThe authors could at least propose some preliminary experimental designs, which would significantly strengthen the paper. For example, one could verify that graph products enhance the expressive power of persistent homology (PH) on synthetic graphs [1]. \n```\nThe Table below shows the accuracy results of different topological descriptors in distinguishing pairs of graphs of the BREC benchmark [1]. We compare our proposal (GraphProd) against PH (vertex and edge filtrations) and RePHINE [3]. We consider different filtration functions: degree, betweenness centrality, closeness centrality and Forman-Ricci curvature. Surprisingly, GraphProd distinguishes all graphs, including the challenging ones: Distance Regular (DR) and strongly regular (STR), for which the other descriptors cannot distinguish any pair. This highlights the expressive power of using graph products for detecting graph isomorphism.\n\n| **Filtration**   | **Diagram**       | **Reg** | **Ext** | **Basic** | **DR** | **STR** |\n|------------------|-------------------|--------:|--------:|----------:|-------:|-------:|\n| **Degree**       | PH$^V$ |    0.00 |    0.07 |      0.03 |   0.00 |   0.00 |\n|                  | RePHINE           |    0.94 |    0.77 |      0.97 |   0.00 |   0.00 |\n|                  | GProd$^V$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n| **Betweenness**  | PH$^V$ |    0.96 |    0.82 |      0.95 |   0.00 |   0.00 |\n|                  | RePHINE           |    0.98 |    0.94 |      1.00 |   0.00 |   0.00 |\n|                  | GProd$^V$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n| **Closeness**    | PH$^V$ |    0.26 |    0.46 |      0.27 |   0.00 |   0.00 |\n|                  | RePHINE           |    0.98 |    0.88 |      1.00 |   0.00 |   0.00 |\n|                  | GProd$^V$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n| **FR Curvature** | PH$^E$ |    0.94 |    0.70 |      0.97 |   0.00 |   0.00 |\n|                  | GProd$^E$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n\n\n\n```\nAdditionally, for a graph classification task, it would be valuable to compare the effectiveness of PH and Euler characteristic (EC) under the graph product structure, observing the performance improvements of classification models [2].\n```\nTo assess the effectiveness of product filtration (Theorem 4) in real-world classification tasks, we can employ classifiers as in the following:\n\n1. **Define a family of small reference graphs**. We selected eight graphs generated using the NetworkX library: nx.cycle_graph(4),nx.complete_graph(5),nx.star_graph(5), nx.lollipop_graph(3,3),nx.watts_strogatz_graph(10,2,0.2),nx.turan_graph(5,2), nx.house_graph();\n\n2. **Compute pairwise product filtrations**. For an incoming graph G, we compute the product filtration (using betweenness centrality as filtration function) between G and each reference graph. This will result in 8 persistence diagrams.\n\n3. **Vectorize the diagrams**. We vectorize the obtained diagrams from previous step using any suitable scheme (e.g., DeepSets or the methods in [2]). In this work, we applied Gaussian vectorization [2] with q=10\n\n4. **Merge topological and GNN embeddings**. We concatenate the topological embeddings with GNNs embeddings before sending it through a classification head.\n\n   \nWe are interested in assessing if these topological descriptors based on graph products can improve the performance of GNNs. We considered 2 GNN models: GIN and GraphSAGE with either 2, 3 or 4 layers (selected via validation set). We assessed the models in 4 real-world datasets: NCI1, NCI109, ZINC, and PROTEINS. Here are the results (over 5 seeds):\n\n| Model                   | PROTEINS   | NCI1      | NCI109    | ZINC      |\n|-------------------------|------------|-----------|-----------|-----------|\n| **GIN**                 | 68.75 ± 1.55 | 80.62 ± 0.37 | 76.67 ± 1.61 | 0.58 ± 0.01 |\n| **GIN + ProdFiltration**| 69.05 ± 2.25 | 81.43 ± 0.51 | 77.72 ± 1.37 | 0.58 ± 0.01 |\n| **SAGE**                | 69.35 ± 2.25 | 77.62 ± 3.05 | 77.80 ± 1.38 | 0.54 ± 0.01 |\n| **SAGE + ProdFiltration**| 70.24 ± 2.87 | 78.02 ± 2.03 | 78.29 ± 1.46 | 0.52 ± 0.01 |\n\nAs we can see, the topological descriptors lead to boost across most combinations of GNNs and datasets. Overall, this illustrates the practical relevance of our contribution. We will add this to the revised manuscript.\n\n**Experimental Validations of Run-Times for Theorem 4 and 5:**\nFor the runtime experiments of vertex-level product filtration, we considered three algorithms - one based on **Theorem 4**, one performing a naive calculation on the entire graph product using the union-find PH code outlined in Algorithm 1 of [2], and one performing a naive calculation using the **gudhi** library's PH code. We note that the **gudhi** library's PH code is very optimized and industry standard. We used the BREC dataset [3] for the data. For each dataset we considered, we load in two graphs G, H each time. We assign them vertex labels being the degree (ie. fv = deg) as the color and then compute the PH of G \\Box H.\n\nThe following table reports the average runtime (in seconds, taken over 10 trials) each algorithm took to go over the entire dataset.\n| **Method**       | **Basic**|**STR** | **DR** | **CFI**|\n|-------------------|--------|--------|----------|-------|\n|Theorem 4 (ours)| **0.967** |**2.040**|**1.554**|**31.253** |\n|Naive PD|1.427|33.691|22.569|673.253|\n|gudhi|1.091|16.469|10.243| 106.463| \n\nFor experiments of edge-level product filtration, we considered again **Theorem 5**, naive PD with union find, and gudhi. The edge filtration function is given by an augmented Forman–Ricci curvatu with $f_e(u, w) = 4 - |N(u)| - |N(w)| + 3|N(u) \\cap N(w)| + 2 n$, where $N(u)$ is the neighboring vertices of $u$ and $n_ is the number of total vertices. The following table shows the average time (in seconds) taken over 10 trials.\n| **Method**       | **Basic**|**STR** | **DR** | **CFI**|\n|-------------------|--------|--------|----------|-------|\n|Theorem 5 (ours)|0.859|**1.527**|**1.055**|**5.899**|\n|Naive PD|1.465|38.828| 24.138 |742.611|\n|gudhi| **0.065**|4.110| 2.179 |32.111| \n\nWe can see that as the graph data gets larger, our **Theorem 4 and 5** significantly outperforms the other two methods here. We also analyzed the theoretical complexity of the two theorems. For more details on that, please see our response to **Reviewer quwK**.\n\n### Section 3\n```\nIn particular, Section 3 feels disconnected and could be moved to the appendix to allow the main text to focus more clearly on topological descriptors for graph products.\n```\nWe agree as well - we will need space to add in the experiments.\n\n-----\nMany thanks for your insightful review and constructive feedback. We hope your concerns have been satisfactorily addressed, and if so, would appreciate if you could revisit your score to reflect the same. We are also committed to engaging further if you have any additional questions, concerns, or suggestions.\n\n[1] Towards Better Evaluation of GNN Expressiveness with BREC Dataset, ICLR 2024.\n\n[2] PersLay: A Neural Network Layer for Persistence Diagrams and New Graph Topological Signatures, AISTATS 2021.\n\n[3] Immonen et al, Going beyond persistent homology using persistent homology.NeurIPS 2024."}, {"review_id": "A9z7cLVmvU", "reviewer": "Reviewer_quwK", "summary": "This paper studies persistent homology (PH) and Euler characteristics (EC) of graph products and present several new theoretical results. The authors introduce a computationally cheaper variant of EC, called max-EC, and proves that it has the same expressive power for graphs and fore higher-dimensional simplicial complexes. It is shown that PH on graph products captures strictly more structural information than PH on individual graphs, while EC does not capture more information on graph products. The authors present new algorithms for computing PH persistence pairs (0 and 1 dimensional) for vertex/edge-level product filtrations, and new characterizations of product filtrations via colorings on graph products. As application, the authors propose to use graph product filtrations as enhanced topological descriptors in GNN.", "questions": "- The proposed algorithms for PH on product filtrations track births-deaths inductively, which seems expensive to scale. Do the authors has any estimation of their computational complexity for large graphs?\n  \n- The authors suggest that graph products can better capture relational data structures. Could the authors give some experiments or discuss some use cases where graph product aware PH improves GNN performance? Will the improvement outweigh the cost of product filtration computations?\n\n- While using virtual nodes can boost PH expressivity, does it change or add some artificial features (like circles or cliques) to the graphs? If it does, how do the additional features affect the descriptors? How to choose f_v and f_e?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n- To my knowledge, max-EC and the virtual node technique for boosting PH expressivity in graph products are new.  max-EC gives a lightweight, theoretically grounded alterative to EC. Virtual nodes have been used to improve expressivity of GNN, but its use in TDA seems new.\n- The combinatorial characterization of EC expressivity for graphs and simplicial complexes, as well as the study of PH/EC on graph products are highly valuable to topological data analysis. max-EC and PH might be useful for exploiting graph product structures in GNN.\n- The proofs (edge and vertex color counting arguments, filtration refinements, Betti number calculations) look sound to me. The authors acknowledge that their algorithms for persistence pairs only apply to product filtrations, not general color-based filtrations.\n\n Weaknesses:\n- It lacks discussions on computational complexity and scalability of the proposed algorithms for PH on product filtrations.\n  \n- It lacks experiments or concrete use cases where graph product aware PH improves GNN performance.\n\n- It lacks discussion on the effects of virtual nodes on additional graph features and the appropriate choice of f_v and f_e.", "was_revised": true, "final_justification": "The original theoretical results are new and interesting and constitute a nice contribution to topological data analysis. During the rebuttal phase, the authors provide new results on complexity analysis and experimental results. They promise to revise the paper to incorporate new results provided during the rebuttal. Overall, the theoretical results are valuable contribution which justifies my rating of the paper.", "rebuttal": "Thank you for your review and suggestions. We reply to your comments/questions below.\n\n```\nIt lacks discussions on computational complexity and scalability of the proposed algorithms for PH on product filtrations. ... Do the authors has any estimation of their computational complexity for large graphs?\n```\nThank you for this question! We have now implemented **Theorem 4** and **Theorem 5** in Python, and we will discuss their theoretical complexity and empirical runtime here.\n\nFor a connected graph with m edges, its PH can be calculated in O(mlog(m)) time (see the discussion before 4.1 in [1]). If the graph is not connected, it is O(n + mlog(m)) where n is the number of vertices - to account for the worst-case scenario where the graph is totally disconnected.\n\nNow, let G be a graph with nG nodes, mG edges, H be graph with nH nodes, mH edges, and X be the coloring set for G and H. \n\nFor **Theorem 5**, the algorithm does not need to compute the graph product and is dependent on the PH for G and PH for H separately. We can precompute the number of non-trivial deaths and number of vertices still alive in O(nG log(nG)) and O(nH log(nH)) time by sorting the two PH diagrams by death-times and count accordingly. Then we loop through both lists in parallel to compute the diagram. Thus, the runtime of Theorem 5 would be $O(max(nG log(nG)+nH log(nH), mG log(mG) + nG, mH log(mH) + nH))$.\n\nFor **Theorem 4**, the algorithm also does not need to compute the product of the two graphs. We can similarly compute the two individual persistence diagrams in $O(mG log(mG) + nG)$ and $O(mH log(mH) + nH)$ time. We can pre-compute the relevant data from the diagrams similarly. If we assume X has constant size, then this can in fact be done in linear time. We initialize the persistence diagram with nG nH tuples with empty entries. In this case, when we loop through the filtration steps, our current (unoptimized) code implements the intermediate steps in the Theorem by looping through the nG*nH tuples. This yields the runtime as O(nG nH + mG log mG + mH log mH + nG + nH).\n\nIn contrast, a naive calculation for vertex-level and edge-level pproduct filtrations would be to run PH on the graph product directly. This incurs a runtime of O(nG nH + (nG mH + nH mG) log(nG mH + nH mG)).\n\n**Theorem 4** and **Theorem 5** empirically perform significantly better than the naive implementations.\n\nFor the runtime experiments of vertex-level product filtration, we considered three algorithms - one based on **Theorem 4**, one performing a naive calculation on the entire graph product using the union-find PH code outlined in Algorithm 1 of [2], and one performing a naive calculation using the **gudhi** library's PH code. We note that the **gudhi** library's PH code is very optimized and industry standard. We used the BREC dataset [3] for the data. For each dataset we considered, we load in two graphs G, H each time. We assign them vertex labels being the degree (ie. fv = deg) as the color and then compute the PH of G \\Box H.\n\nThe following table reports the average runtime (in seconds, taken over 10 trials) each algorithm took to go over the entire dataset.\n| **Method**       | **Basic**|**STR** | **DR** | **CFI**|\n|-------------------|--------|--------|----------|-------|\n|Theorem 4 (ours)| **0.967** |**2.040**|**1.554**|**31.253** |\n|Naive PD|1.427|33.691|22.569|673.253|\n|gudhi|1.091|16.469|10.243| 106.463| \n\nFor experiments of edge-level product filtration, we considered again **Theorem 5**, naive PD with union find, and gudhi. The edge filtration function is given by an augmented Forman–Ricci curvatu with $f_e(u, w) = 4 - |N(u)| - |N(w)| + 3|N(u) \\cap N(w)| + 2 n$, where $N(u)$ is the neighboring vertices of $u$ and $n$ is the number of total vertices. The following table shows the average time (in seconds) taken over 10 trials.\n| **Method**       | **Basic**|**STR** | **DR** | **CFI**|\n|-------------------|--------|--------|----------|-------|\n|Theorem 5 (ours)|0.859|**1.527**|**1.055**|**5.899**|\n|Naive PD|1.465|38.828| 24.138 |742.611|\n|gudhi| **0.065**|4.110| 2.179 |32.111| \n\nFinally, we analyze the theoretical costs of **Proposition 8**. For A and B graphs, since the quantity b1(A \\Box B) can be expressed in terms of the number of edges (1), the number of connected components (2), and the number of vertices (3) of A and B respectively. To compute the 1-dim persistence diagram of a product filtration, it suffices for us to keep track of how (1), (2), (3) changes over time. These can all be done in a time dominated by O(mG log mG + nG + mH log mH + nH) (ie. the time to compute the persistence diagrams), which still outperforms the naive method.\n\n```\nIt lacks experiments or concrete use cases where graph product aware PH improves GNN performance. [...] Could the authors give some experiments or discuss some use cases where graph product aware PH improves GNN performance? \n```\nThank you for your comment. First, we emphasize that the proposed descriptors capture structural information that GNNs (1-WL) fail to detect. In particular, our topological descriptors distinguish all pairs of graphs in the BREC dataset [3], which is specifically designed to assess the expressivity of graph models.\n\nThe accuracy results (fraction of identified non-isomorphic graph pairs) are:\n| **Filtration**   | **Diagram**       | **Reg** | **Ext** | **Basic** | **DR** | **STR** |\n|------------------|-------------------|--------:|--------:|----------:|-------:|-------:|\n| **Degree**       | PH$^V$ |    0.00 |    0.07 |      0.03 |   0.00 |   0.00 |\n|                  | RePHINE           |    0.94 |    0.77 |      0.97 |   0.00 |   0.00 |\n|                  | GProd$^V$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n| **Betweenness**  | PH$^V$ |    0.96 |    0.82 |      0.95 |   0.00 |   0.00 |\n|                  | RePHINE           |    0.98 |    0.94 |      1.00 |   0.00 |   0.00 |\n|                  | GProd$^V$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n| **Closeness**    | PH$^V$ |    0.26 |    0.46 |      0.27 |   0.00 |   0.00 |\n|                  | RePHINE           |    0.98 |    0.88 |      1.00 |   0.00 |   0.00 |\n|                  | GProd$^V$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n| **FR Curvature** | PH$^E$ |    0.94 |    0.70 |      0.97 |   0.00 |   0.00 |\n|                  | GProd$^E$ (ours)  |    1.00 |    1.00 |      1.00 |   1.00 |   1.00 |\n\nRegarding real-world experiments, we consider 4 classification tasks and 2 GNNs: GIN and GraphSAGE. The results (over 5 seeds) are in the Table below.\n\n\n| Model                   | PROTEINS   | NCI1      | NCI109    | ZINC      |\n|-------------------------|------------|-----------|-----------|-----------|\n| **GIN**                 | 68.75 ± 1.55 | 80.62 ± 0.37 | 76.67 ± 1.61 | 0.58 ± 0.01 |\n| **GIN + ProdFiltration**| 69.05 ± 2.25 | 81.43 ± 0.51 | 77.72 ± 1.37 | 0.58 ± 0.01 |\n| **SAGE**                | 69.35 ± 2.25 | 77.62 ± 3.05 | 77.80 ± 1.38 | 0.54 ± 0.01 |\n| **SAGE + ProdFiltration**| 70.24 ± 2.87 | 78.02 ± 2.03 | 78.29 ± 1.46 | 0.52 ± 0.01 |\n\n\nWe refer to our answer to Reviewer MD6t for further details on the experiments.\n\n```\nWill the improvement outweigh the cost of product filtration computations?\n```\nWe note that combining product filtrations with GNNs scales very efficiently. Because these filtrations can be pre-computed, they introduce only a minor overhead to the standard GNN pipeline. Recall that, in product filtrations, we do not compute the Cartesian product between the graphs.\n\nIn particular, the theoretical and empirical computational costs of the computational algorithms outlined in Section 5 are quite promising. Please see our response to the first weakness you pointed out above for more details.\n\n```\nIt lacks discussion on the effects of virtual nodes on additional graph features and the appropriate choice of f_v and f_e ... While using virtual nodes can boost PH expressivity, does it change or add some artificial features (like circles or cliques) to the graphs? If it does, how do the additional features affect the descriptors? How to choose f_v and f_e?\n```\nThank you for raising the question. For our case, we adjoin a virtual node to a graph G as a disjoint basepoint that is born at time negative infinity (ie. at the very start), write G_+ as G adjoined the virtual node. Note that this is different from what some other people might call ``virtual\" (such as adding a fully adjacent node to connect to the entire graph, ie. [4]). In our case, adding a disjoint vertex to G does not increase the number of circles or cliques (unless you allow isolated vertices to be cliques in the definition), but it will add an extra component. The effect of having a virtual node is more significant for graph products. For both G and H, G_+ \\Box H_+ is exactly the disjoint union of four graphs: an isolated node, a copy of G, a copy of H, and G \\Box H. This is done to guarantee that a filtration of G_+ \\Box H_+ also goes through G and H individually (which is possible because we also assign the virtual a distinct color away from the existing coloring set). To go through G and H first, one should choose fv and fe such that they spawn G and H first in the series (or at least in an isolated time interval).\n\n----------\nMany thanks for your insightful review and constructive feedback. We hope your concerns have been satisfactorily addressed, and if so, would appreciate if you could revisit your score to reflect the same. We are also committed to engaging further if you have any additional questions, concerns, or suggestions.\n\n[1] Horn et al, Topological graph neural networks,ICLR 2022.\n\n[2] Immonen et al, Going beyond persistent homology using persistent homology.NeurIPS 2024.\n\n[3] Wang et al, Towards Better Evaluation of GNN Expressiveness with BREC Dataset,ICLR 2024.\n\n[4] Alon et al, On the Bottleneck of Graph Neural Networks and its Practical Implications,ICLR 2021."}]

Author rebuttal:

Meta-review: # Summary

This paper proposes a novel framework for studying topological descriptors, viz., the Euler characteristic (EC) and persistent homology (PH), on graph products under so-called color-based filtrations. As its main contributions, the paper characterizes expressivity with respect to the EC and the PH on color-based filtration; it also provides algorithms for calculating such topological descriptors for graph products.

# Strengths

- Rigorous theory for a novel application
- The work is broadly relevant for the "topology in ML" community, since it not only improves the foundation of TDA/TDL, but also provides new tool for graph ML.
- The rebuttal provided more insights into the practical applicability of the work and its integration with GNNs.

# Weaknesses

- In the current version of the manuscript, experiments are _absent_, raising concerns about maturity and practical relevance.
- The paper's writeup is quite dense, requiring a large degree of technical acumen to parse.
- In original submission, the practical aspects and relevance for the ML community was somewhat underdeveloped, but the rebuttal served to alleviate these concerns.
- The exposition of the paper could be improved

# Decision and rationale

All reviewers agreed on the relevance and quality of this work and I am happy to suggest _accepting_ it for the conference. However, this verdict is contingent on providing additional empirical experiments and strengthening the "broader appeal" of the work. While the authors provided an excellent rebuttal, some reviewers raised concerns about this submission being essentially "incomplete," insofar as no experiments were present in the original version. I concur with this assessment but I believe that a strong NeurIPS paper can also be written from the purely theoretical point of view. As such, it should not be unduly penalized. That being said, I expect the authors to use the feedback re: clarity and utility to improve their work in a revision.

# Summary of the discussion

- Reviewer `MD6t`: Leaned towards accepting the paper; citing concerns about readability and overall completeness of the work. Authors promised improvements, which partially addressed the reviewer's concerns.

- Reviewer `Ytkj`: Endorse the paper after the rebuttal, since the authors provided additional experiments and promised a clearer motivation.

- Reviewer `ETh2`: Leaned towards accepting the paper but mentioned issues with exposition; authors promised to address these concerns in a revision.

- Reviewer `6YNL`: Was concerned about the lack of experiments; raised their score after authors promised new experiments.

- Reviewer `quwK`: Appreciated the theoretical results, but cited concerns about premature submission with major results being missinga and only appearing in the rebuttal. Authors promised changes and were able to provide additional clarifications; I share these concerns and thus base my overall positive verdict on the authors' willingness to implement these changes.

The rebuttal proved to be highly useful in this case, with many reviewers engaging very strongly with the authors.
Decision: Accept (poster)