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

It 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?

Thank 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.

For 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.

Now, 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.

For 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))$.

For 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).

In 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)).

Theorem 4 and Theorem 5 empirically perform significantly better than the naive implementations.

For 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.

The following table reports the average runtime (in seconds, taken over 10 trials) each algorithm took to go over the entire dataset.

For 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.

Finally, 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.

It 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? 

Thank 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.

The accuracy results (fraction of identified non-isomorphic graph pairs) are:

Regarding real-world experiments, we consider 4 classification tasks and 2 GNNs: GIN and GraphSAGE. The results (over 5 seeds) are in the Table below.

We refer to our answer to Reviewer MD6t for further details on the experiments.

Will the improvement outweigh the cost of product filtration computations?

We 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.

In 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.

It 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?

Thank 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).

---

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

[1] Horn et al, Topological graph neural networks,ICLR 2022.

[2] Immonen et al, Going beyond persistent homology using persistent homology.NeurIPS 2024.

[3] Wang et al, Towards Better Evaluation of GNN Expressiveness with BREC Dataset,ICLR 2024.

[4] Alon et al, On the Bottleneck of Graph Neural Networks and its Practical Implications,ICLR 2021.

Plans for revision

There are some previous works on learning product spaces which is missing ... how will the author plan to discuss ... related works and compare the performance between capturing graph product structures using persistent homology and learning it automatically

Thank you for your suggestions to strengthen our work.

Experiments

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.

Thanks for your comment. As suggested, we have added three sets of experiments:

1. expressivity on BREC datasets --- here, surprisingly, we found that simple filtration functions on Graph Products can distinguish all pairs of graphs on BREC.

2. graph classification on NCI1, NCI109, PROTEINS, ZINC. Here, we showed that the topological descriptors consistently boost the performance of GNNs (SAGE, GIN).

3. Experimental validations for the runtime benefits of the proposed algorithms in Theorem 4 and Theorem 5.

Please, see the next answers for details and results.

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]. 

The 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.

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].

To assess the effectiveness of product filtration (Theorem 4) in real-world classification tasks, we can employ classifiers as in the following:

1. 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();

2. 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.

3. 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

4. Merge topological and GNN embeddings. We concatenate the topological embeddings with GNNs embeddings before sending it through a classification head.

We 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):

As 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.

Experimental Validations of Run-Times for Theorem 4 and 5: For 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.

The following table reports the average runtime (in seconds, taken over 10 trials) each algorithm took to go over the entire dataset.

For 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.

We 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.

Section 3

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.

We agree as well - we will need space to add in the experiments.

---

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

[1] Towards Better Evaluation of GNN Expressiveness with BREC Dataset, ICLR 2024.

[2] PersLay: A Neural Network Layer for Persistence Diagrams and New Graph Topological Signatures, AISTATS 2021.

[3] Immonen et al, Going beyond persistent homology using persistent homology.NeurIPS 2024.

Thank you for your review - we reply below.

... theoretical formulation are dense, ... may cause some difficulty for following for people without similar background.

Thanks 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.

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. [...] can you provide some experimental results for verification?

Thanks for your comment. We evaluate expressivity using the BREC datasets~\cite{brec}.

Given a pair of graphs $G$ and $H$, we apply persistent homology (PH) on graph products to decide graph isomorphism as follows:

1. Compute the persistence diagrams for $G \Box G$ and $G \Box H$. If the diagrams differ, we conclude that $G$ and $H$ are not isomorphic. Otherwise, proceed to Step~2.

2. Compute the persistence diagrams for $G \Box G$ and $H \Box H$. If these diagrams differ, we 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 (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.

[1] Towards Better Evaluation of GNN Expressiveness with BREC Dataset, ICLR 2024.

[2] PersLay: A Neural Network Layer for Persistence Diagrams and New Graph Topological Signatures, AISTATS 2021.

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.

Please 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.

Here we summarize the main points.

1. For Theorem 5, the runtime is $O(max(nG log(nG)+nH log(nH), mG log(mG) + nG, mH log(mH) + nH))$.

2. 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)$.

3. 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.

4. 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).

Can we use the proposed descriptors to improve the traditional GNN expressiveness? Or how to use them for practical tasks?

Thanks 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:

1. 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();

2. 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.

3. 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

4. Merge topological and GNN embeddings. We concatenate the topological embeddings with GNNs embeddings before sending it through a classification head.

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:

As 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.

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?

Computational 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.

We 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.

In 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

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?

The 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.

We are grateful for your time and comments. We reply to your comments/questions below.

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.

Thanks for your comment. We conducted two sets of experiments to demonstrate the practical relevance of our paper.
First, 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:

In 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:

1. 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();

2. 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.

3. 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

4. Merge topological and GNN embeddings. We concatenate the topological embeddings with GNNs embeddings before sending it through a classification head.

We consider GINs (graph isomorphism networks) and GraphSAGE. The results are:

As we can see, the topological descriptors consistently yield improvements across most GNN–dataset combinations, underscoring the practical significance of our contribution.

[1] Towards Better Evaluation of GNN Expressiveness with BREC Dataset, ICLR 2024.

[2] PersLay: A Neural Network Layer for Persistence Diagrams and New Graph Topological Signatures, AISTATS 2021.

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.
...
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.

Thank you for raising this question! Here, we elaborate on why graph products show up in terms of relational databases.

Recall 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).

Suppose 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.

Now 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.

Thus, we see that graph products show up naturally in the context of relational databases, and we will expand on this in the introduction.

We 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.

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.

Thank 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.

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.

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).

Please see more details in the response to Reviewer quwK.

---

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

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

Motivation

The 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.

Thank 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.

Relational Databases: Recall 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).

Suppose 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.

Now 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.

Thus, we see that graph products show up naturally in the context of relational databases, and we will expand on this in the introduction.

Expressivity Tests: Another 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:

Typos

Line 65: “A graph is a the…” -> “A graph is the data…”?

Thanks for catching this. We will fix it in the revision.

In line 65, shouldn’t it be E \subset V x V, instead of E \subset V x X

Thanks for catching the typo. We will fix it in the revision.

Line 91-92: What do you mean by “filtration of a diagram”?

Thanks for catching the typo, we meant graph instead of diagram. We will fix it in the revision.

Color Filtrations

The choice of notation for Fv seems slightly confusing...

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.

The 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. 

Thank 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.

$(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.

For 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.

Therefore, 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])

This 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.

what is the point of the coloring function c? One could just consider f_v o c ...

The 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.

We 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.

Moreover, it seems like this is an analysis of a bifiltration over a graph where fv and fe are two different filtrations.

Thank 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!

---

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

[1] Towards Better Evaluation of GNN Expressiveness with BREC Dataset, ICLR 2024.

[2] Immonen et al, Going beyond persistent homology using persistent homology.NeurIPS 2024.

[3] On the Expressivity of Persistent Homology in Graph Learning. Ballester and Rieck.

Thank you for your continued engagement. We respond to your concerns/comments as follows.

Well, for testing for graph isomorphism, one can consider a simple vertex degree based filtration, which would be sufficient to test for graph isomorphism using PH. I am not fully convinced by this argument.

Thank you for the opportunity to clarify our work. The example you gave here can be seen as an example of assigning colors to unlabeled graphs. In this case, the colors on each vertex would be its degree, and the degree-based filtration you described would be to spawn the vertices according to their degrees from lowest to highest, and an edge is spawned if both of its vertices are spawned.

However, this is only one way to spawn the vertices. We could have also spawned the vertices according to their degrees from highest to lowest. The perspective of coloring filtration is that we can spawn the vertices in any permutation of the set of possible degree values here. For example, if the set of degrees from two graphs G and H are {1, 3, 5, 8}. A typical degree-based filtration would be to spawn all the vertices of degree 1 first, then degree 3, then degree 5, and finally degree 8. The perspective of coloring filtration is to consider all possible permutations - ie. 1-3-5-8, 1-3-8-5, 3-1-5-8, 3-8-5-1, etc... - for which we can take PH.

In practice, one sometimes cannot test all possible permutations, but doing the degrees sequentially in time is only 1 of the n! possibility. The perspective of coloring filtration is that one should not prefer a permutation over another. In general, there are pairs of non-isomorphic graphs such that taking the PH of their degree-based filtration (lowest to highest) cannot differentiate, but taking the PH of their degree-based filtration in a different order does. And this is only one of the other possible colors in general.

For example, let G (left) and H (right) be the following 2 non-isomorphic graphs made in the networkX library

G = nx.from_edgelist([(0, 1), (1, 2), (2, 3), (1, 4), (4, 5)])
H = nx.from_edgelist([(0, 1), (1, 2), (1, 3), (3, 4), (4, 5)])

In this case, the possible vertex degrees are 1, 2, 3. Running PH on the vertex degree-based filtration (the version you proposed) will not be able to differ them (this is the order 1-2-3), neither would doing this in the order 3-2-1. However, we can differentiate the 2 graphs in the order 2-3-1. Indeed, if we load all the vertices labeled the color/degree '2' first, we would get 2 connected components in G but 1 connected component in H. Thus, there are graphs that a traditional degree filtration cannot differ but coloring filtrations can.

We also note that a vertex degree-based filtration did not manage to differentiate the majority of pairs of graphs in the BREC dataset (see our table in the initial rebuttal comment with PH$^V$). However, if we incorporate alternative colors in, it could potentially increase their expressivity over them.

I understand the point the authors are trying to make. However, I do not see the point in it because, eventually, even if you do retain information about specific attributes of the graph, computing PH is going to get the topological information into numerical data (either index-persistence or real-number persistence).

Thank you for your question. In light of the explanation above, we hope it makes more sense why we wanted attributes to be in X. This is because the coloring filtration considers all the possible permutations of colors rather than a single order. Having the colors stored numerically may lead to some confusion since R has a natural order.

That being said, we also do not see any major issues with labeling the colors into numerical attributes to begin with, which is an example of assigning colors. In the perspective of coloring filtrations, they are just assigning ids to the vertices. The usual filtration in the order of numerical values is a special example of a coloring filtration where $f_v$ is the identity.

For example, if we have a graph G where the set of numerical values are the vertices are {56, 90.4, 101.7}. We can spawn in all the vertices labeled 56 first, and then 90.4, and finally 101.7. Or we can down 90.4 first, and then 101.7, and finally 56. There are 6 possibilities in total here. The essence of coloring filtrations just asks to consider alternative orders to filtrate than the usual sequential one.

---

Many thanks for your questions! We hope this addresses your concerns, and, if so, would appreciate if you could change your rating to reflect the same.

[1] Towards Better Evaluation of GNN Expressiveness with BREC Dataset, ICLR 2024.

 I suggested a simple degree based filtration for the case when G and H are isomorphic. However, the example given is the case where the graphs are non-isomorphic to begin with and hence is a non-example.