TopER: Topological Embeddings in Graph Representation Learning

We thank the reviewer for their valuable feedback, which, along with comments from others, has guided significant improvements to our paper.

W1. Linear Regression

The reason of adapting linear regression to fit the filtration sequences is mentioned in the Appendix, yet no theoretical or experimental support are provided.

Thank you for your insightful question. From a mathematical perspective, it is indeed possible to construct examples where higher-degree fitting functions outperform a linear fit. However, such cases are exceptional due to the following reasons:

Let $x_i = |V_i|$ and $y_i = |E_i|$, where $G_i = (V_i, E_i)$ represents a subgraph in the filtration sequence {$G_i$} for $1\leq i\leq N$. The problem reduces to finding the best fit for $N$ points $Q = \{(x_i, y_i)\}_{i=1}^N$.

Observations

1. Monotonicity of Sequences:
   Both $\{x_i\}$ and $\{y_i\}$ are monotone non-decreasing sequences. By appropriately selecting thresholds and ignoring repetitions, these sequences can be assumed to be strictly monotone increasing. Consequently, $Q$ lies on the graph of an increasing function $y = f(x)$.

2. Behavior of $f(x)$:
   The nature of $f(x)$ determines the fitting model:

   • Linear Fit (Order 1): $y = ax + b$
   • Quadratic Fit (Order 2): $y = ax^2 + bx + c$ (convex or concave)
   • Higher-Order Fits: These correspond to cases where the curve exhibits mixed convex and concave behavior.

The behavior of $f(x)$ depends on the rate of change, captured by the sequence $\Delta_i = \frac{y_{i+1} - y_i}{x_{i+1} - x_i}$:

• Linear Fit: $\Delta_i$ is approximately constant.
• Quadratic Fit: $\Delta_i$ is either monotonically increasing (convex) or decreasing (concave).
• Higher-Order Fits: $\Delta_i$ does not follow a monotone pattern.

Experimental Insights

In our experiments, we did not observe non-monotonic behavior in $\{\Delta_i\}$, eliminating the need for higher-order fits. Instead, we compared linear (order 1) and quadratic (order 2) fits. Interestingly, the linear fit consistently provided better approximations. This is because, for most quadratic fits, the coefficient of the quadratic term was negligibly small, indicating a near-linear relationship.

To support these findings, we provide plots in Appendix B.3, illustrating the behavior of $f(x)$ under various fitting models. Furthermore, we conducted the following experiments to further validate the robustness of the linear fit. In the table below, you can see the average of the coefficients of quadratic terms when we use quadratic fit for the datasets, i.e. if we fit $y=a+bx+cx^2$ polynomial, we observe that quadratic term is mostly negligible, and the tends to be a linear fit. We added this table to Appendix Section B.3.

Here’s the transposed table:

W2. Missing parts of Repo

The key parts of TopER's implementation are missing from the provided repo link.

We apologize for the problem. Due to the blind submission requirement, we used an anonymous GitHub link to share our code. However, for some reason, while the repository exists in the folders, it does not display correctly via the anonymous link at https://anonymous.4open.science/r/TopER-AA38

However, the original repo can be viewed at https://github.com/AstroComets/TopER

W3. Filtration function descriptions

The used filtration functions require further introduction and explanation.

Thank you for this feedback. We added detailed descriptions of filtration functions to Appendix D.

Q1. Repository empty

The functions_to_calculate_[a,b] folder in the anonymous repository appears to be empty. Could you explain why?

Answered above.

Q2. Correlation between a and b?

Is there a theoretical basis for the linear correlation between a and b? How would the model performance when applying other fitting functions, such as polynomials?

Answered above.

Thank you once again for your valuable feedback. We are happy to address any further questions or comments you may have.

We thank the reviewer for their valuable feedback, which, along with comments from others, has guided significant improvements to our paper. We hope our revisions and responses merit reconsideration of a higher evaluation.

W1. Lack of Threshold Setting Details:

The paper does not explain how thresholds are set for different filtration functions, nor how the number of subgraphs n is determined. Since both threshold choice and n could impact results, further analysis would be valuable.

Thank you for this question. We had used 500 thresholds to capture finer-grained information, as the model is computationally efficient and adding more thresholds incurs minimal additional cost. Based on your review, we experimented with more thresholds and found that TopER remains robust and highly effective. We have added this table to Appendix Section A.4.

W2. Clarity on Embedding Dimension:

The paper lacks details on TopER’s final embedding dimension and does not directly compare it to the embedding dimensions of other algorithms. Embedding dimension is crucial for evaluating performance and computational efficiency, so specifying and comparing the dimensions of different methods would enhance the clarity and interpretability of the results.

Thank you for raising this important question. In our experiments, we used the same six filtration functions across all datasets, employing both sublevel and superlevel filtrations, along with an additional atomic weight filtration function specifically for molecular datasets. Each filtration function produces a 2-dimensional TopER embedding, resulting in a total of 24 dimensions per dataset (6 functions× 2 filtrations x 2) or 28 dimensions for molecular datasets. To optimize performance and reduce redundancy, we applied a feature selection algorithm as part of our ML pipeline to identify the most informative features while mitigating the impact of correlated dimensions. The final dimensions after feature selection are given below. We have also incorporated this table into Table 7 (Hyperparameters table).

For the embedding dimensions of other methods, vanilla persistent homology embeddings typically correspond to the number of thresholds used in the filtration step. For example, the degree function often results in 10–20 dimensions, while more complex functions like betweenness or closeness centrality can yield 200–300 dimensions. In contrast, recent GNNs generally use embedding dimensions of 48, 64, 128, or even 512, depending on the pooling mechanism. Therefore, TopER operates with significantly lower embedding dimensions compared to these baseline methods, highlighting its computational efficiency.

Details of the TopER embeddings and the feature selection methodology are provided in Section 5.1. Furthermore, the individual performance of each filtration function (based solely on 2-dimensional embeddings) is reported in Table 6, offering insights into the contributions of specific filtration strategies.

W3. Dataset-Specific Dimension Variability:

Line 394 mentions "top-performing combinations of filtration and vectorization for each dataset," which suggests that embedding dimensions might vary across datasets. However, the paper does not clarify what these combinations are or discuss the impact of using different combinations across datasets, especially given the many possible configurations with the eight filtration functions.

Thank you for raising this valid concern. As detailed in the previous response, we start with the same seven filtration functions for all datasets, as detailed in Section 5.1. Our framework chooses the most informative filtrations which we report below. As our results in Table 6 of the article results, TopER performance with individual filtrations is comparable with SOTA and all TopER with 7 filtrations exceed SOTA results.

Additionally, to assess the impact of embedding dimensions, we conducted new experiments evaluating the performance of the TopER model by progressively adding each filtration function step by step. This analysis, reported below, provides insights into how the inclusion of additional filtration functions influences the model's performance. We include this table along with corresponding filtration functions in Appendix Section A.6.

W4. Contribution of Each filtration:

The ablation study does not analyze the effects of each filtration function on individual datasets, missing insights into how specific functions influence results across different types of data.

Thank you for your insightful feedback. We would like to draw your attention to Table 6, which presents the impact of each filtration function on individual datasets. This table aims to provide a detailed analysis of how specific filtration functions influence the results across various types of data. If there are specific aspects you believe we have overlooked, we would be happy to provide further clarification or expand on this analysis in the revision.

Thank you once again for your valuable feedback. We are happy to address any further questions or comments you may have.

Thank you for all the provided replies, and some of my concerns are addressed. I will keep my rating as 5.

W3. Dataset-Specific Dimension Variability:

Line 394 mentions "top-performing combinations of filtration and vectorization for each dataset," which suggests that embedding dimensions might vary across datasets. However, the paper does not clarify what these combinations are or discuss the impact of using different combinations across datasets, especially given the many possible configurations with the eight filtration functions.

Thank you for raising this valid concern. As detailed in the previous response, we start with the same seven filtration functions for all datasets, as detailed in Section 5.1. Our framework chooses the most informative filtrations. As our results in Table 6 of the article results, TopER performance with individual filtrations is comparable with SOTA and all TopER with 7 filtrations exceed SOTA results.
Additionally, to assess the impact of embedding dimensions, we conducted new experiments evaluating the performance of the TopER model by progressively adding each filtration function step by step. This analysis, reported below, provides insights into how the inclusion of additional filtration functions influences the model's performance. We include the following table along with the filtration functions in Appendix Section A.6.

W4. Contribution of Each filtration:

The ablation study does not analyze the effects of each filtration function on individual datasets, missing insights into how specific functions influence results across different types of data.

Thank you for your insightful feedback. We would like to draw your attention to Table 6, which presents the individual performance of each filtration function on each dataset. This table aims to provide a detailed analysis of specific filtration functions' performances across all datasets. For the synergetic contribution of each filtration function, we refer the table in our previous response. If there are specific aspects you believe we have overlooked, we would be happy to provide further clarification or expand on this analysis in the revision.

Thank you once again for your valuable feedback. We are happy to address any further questions or comments you may have.

We thank the reviewer for their valuable feedback, which, along with comments from others, has guided significant improvements to our paper. We hope our revisions and responses merit reconsideration of a higher evaluation.

W1. Lack of Threshold Setting Details:

The paper does not explain how thresholds are set for different filtration functions, nor how the number of subgraphs n is determined. Since both threshold choice and n could impact results, further analysis would be valuable.

Thank you for this question. We had used 500 thresholds to capture finer-grained information, as the model is computationally efficient and adding more thresholds incurs minimal additional cost. Based on your review, we experimented with more thresholds and found that TopER remains robust and highly effective. We have added this table to Appendix Section A.4.

W2. Clarity on Embedding Dimension:

The paper lacks details on TopER’s final embedding dimension and does not directly compare it to the embedding dimensions of other algorithms. Embedding dimension is crucial for evaluating performance and computational efficiency, so specifying and comparing the dimensions of different methods would enhance the clarity and interpretability of the results.

Thank you for raising this important question. In our experiments, we used the same six filtration functions across all datasets, employing both sublevel and superlevel filtrations, along with an additional atomic weight filtration function specifically for molecular datasets. Each filtration function produces a 2-dimensional TopER embedding, resulting in a total of 24 dimensions per dataset (6 functions× 2 filtrations x 2) or 28 dimensions for molecular datasets. To optimize performance and reduce redundancy, we applied a feature selection algorithm as part of our ML pipeline to identify the most informative features while mitigating the impact of correlated dimensions. The final dimensions after feature selection are given below. We have also incorporated this table into Table 7 (Hyperparameters table).

For the embedding dimensions of other methods, vanilla persistent homology embeddings typically correspond to the number of thresholds used in the filtration step. For example, the degree function often results in 10–20 dimensions, while more complex functions like betweenness or closeness centrality can yield 200–300 dimensions. In contrast, recent GNNs generally use embedding dimensions of 48, 64, 128, or even 512, depending on the pooling mechanism. Therefore, TopER operates with significantly lower embedding dimensions compared to these baseline methods, highlighting its computational efficiency.

Details of the TopER embeddings and the feature selection methodology are provided in Section 5.1. Furthermore, the individual performance of each filtration function (based solely on 2-dimensional embeddings) is reported in Table 6, offering insights into the contributions of specific filtration strategies.

We appreciate your interest in the embedding dimensions and their role in the analysis. If further clarification or additional comparisons to the embedding dimensions of other methods would be helpful, we would be glad to provide them.

W6. Number of Thresholds

Hyperparameter analysis of the number of thresholds is missing.

Thank you for this excellent question. In our experiments, we opted to use a large number of thresholds to capture finer-grained information, as the model is computationally efficient and adding more thresholds incurs minimal additional cost. That said, we also evaluated the model's performance with fewer thresholds and found that it remains robust and highly effective. We have added this table to Appendix Section A.4.

Hyperparameter analysis of the number of thresholds on the number of thresholds.

W7. Missing baselines:

-Immonen, Johanna, Amauri Souza, and Vikas Garg. "Going beyond persistent homology using persistent homology." Advances in Neural Information Processing Systems 36 (2024). -Hofer, Christoph, et al. "Graph filtration learning." International Conference on Machine Learning. PMLR, 2020. -Rieck, Bastian, Christian Bock, and Karsten Borgwardt. "A persistent weisfeiler-lehman procedure for graph classification." International Conference on Machine Learning. PMLR, 2019.

Thank you for bringing these important references to our attention. Since all of these studies used the same experimental setup, we have included their reported results in our accuracy table (Table 2).

Thank you once again for your valuable feedback. We are happy to address any further questions or comments you may have.

W4. Interpretability

Training an MLP on top of (a, b) of different filtration functions also limits the interpretability since the discriminative features may be formed as a combination of different filtration trends. Furthermore, using a single filtration function is always less performative than using multiple functions, which means the evolution rate of no one function is capable of classifying the graphs accurately.

Thank you for your insightful comment. We acknowledge that combining multiple filtration functions can reduce interpretability, as the discriminative features may arise from a complex combination of trends from different filtrations. However, we believe this concern does not detract from the interpretability or performance of our approach in the contexts presented in our paper.

In our work, we apply the TopER model in two distinct ways. The first approach utilizes a single filtration function to generate low-dimensional embeddings, which we use for visualizations. This approach provides highly interpretable results, as the embedding captures the evolution of the graph based on a single, well-defined filtration. Specifically, the parameters from the linear fit $y = ax + b$ (where $a$ represents growth and $b$ is the pivot) are directly interpretable. These parameters summarize the distribution of nodes and edges and the connectivity of the subgraphs induced by the hierarchy of the chosen filtration function. For instance, a large $a$ indicates high connectivity in relation to the filtration, and a negative $b$ suggests low connectivity in the induced subgraphs. We provide detailed illustrations and explanations of these relationships in the main text and in Appendix B.4.

The second approach, involving multiple filtration functions, is used for more complex tasks like graph classification. While we agree that combining different filtrations may reduce the direct interpretability of individual features, it leads to SOTA performance. In our experiments, we show that this synergy between filtration functions improves the model’s ability to capture diverse structural patterns, thus enhancing classification accuracy.

Moreover, many real-world datasets come with their own natural filtration functions—such as transaction amounts for financial networks, density for traffic networks, and power flow for distribution networks—that define meaningful hierarchies among nodes and edges. These domain-specific filtrations further enhance interpretability, as they provide context that aids in understanding the relationships within the data. By leveraging these naturally occurring filtration functions, our model not only achieves strong performance but also remains adaptable to real-world datasets, allowing for effective visualization, cluster detection, and outlier identification.

We believe this dual approach offers a balance between interpretability and performance, and we have demonstrated its effectiveness across multiple domains.

W5. Time complexity PH vs. TopER

A simpler comparison should be provided that compares persistent homology and TopER in their time complexity and graph classification accuracy assuming the same filtration function.

Thank you very much for this feedback. In response to your suggestion, we conducted experiments comparing persistent homology and TopER using the same filtration function, specifically the sublevel degree filtration. For PH, we employed Betti vectorization. Our results, as shown below, demonstrate that TopER is significantly faster than PH.

W2. Attributed graphs?

The method is limited to non-attributed graphs and cannot easily extend to attributed graphs, for which it might depend on other graph kernels to be devised.

Thank you very much for this insightful question. For attributed graphs, node or edge attributes can be effectively leveraged to define filtration functions. In our experiments, we utilized this approach for molecular graphs, where node attributes such as atomic weights provided a meaningful filtration function. Similarly, for transaction networks, one might use transaction amounts as edge filtration functions, and for distribution networks, voltage values could serve as node filtration functions.

When the node attributes are high-dimensional, dimension reduction techniques like tSNE or alphacore (a data depth-based method) can be employed to derive filtration functions that capture the most relevant information. Among our datasets, only BZR and COX2 had high-dimensional node attributes. For these datasets, we used tSNE and alphacore to induce filtration functions, ensuring that the extracted features were both meaningful and computationally efficient. We report the results of these experiments below.

W3. High sensitivity to filtration functions:

As can be noted by the ablation study, the performance is highly sensitive to the filtration functions used for a particular dataset. This limits the strengths since it is not clear if the set of filtration functions considered in this work are even exhaustive.

Thank you for your insightful comment. We appreciate the reviewer's comment on the sensitivity of performance to different filtration functions. Our method is designed to use multiple filtrations to gain different perspectives on the data's structure. Consistent results across individual functions were not our focus. Instead, we aimed to combine their strengths for better outcomes.

For example, degree and closeness filtrations show a high similarity, with a correlation of 0.96. On the other hand, the correlation between degree and Ricci curvature is 0.7, showing that these filtrations bring unique insights. This diversity is a strength of our method, allowing it to capture varied aspects of the data.

As shown in Table 6, TopER's performance when combining these functions is better than using any one function alone. This demonstrates that using multiple filtrations together enhances the method's overall effectiveness- TopER reaches SOTA results.We also note that the individual performance of filtration functions is crucial for visualization, as better performance leads to clearer separation among classes.

W1.2 Why linear

It is not clearly stated why there should be a linear correlation between the two numbers. The motivating figures also do not motivate a linear correlation, except for MUTAG.

Thank you for your insightful question. From a mathematical perspective, it is indeed possible to construct examples where higher-degree fitting functions outperform a linear fit. However, such cases are exceptional due to the following reasons:

Let $x_i = |V_i|$ and $y_i = |E_i|$, where $G_i = (V_i, E_i)$ represents a subgraph in the filtration sequence {$G_i$} for $1\leq i\leq N$. The problem reduces to finding the best fit for $N$ points $Q = \{(x_i, y_i)\}_{i=1}^N$.

Observations

1. Monotonicity of Sequences:
   Both $\{x_i\}$ and $\{y_i\}$ are monotone non-decreasing sequences. By appropriately selecting thresholds and ignoring repetitions, these sequences can be assumed to be strictly monotone increasing. Consequently, $Q$ lies on the graph of an increasing function $y = f(x)$.

2. Behavior of $f(x)$:
   The nature of $f(x)$ determines the fitting model:

   • Linear Fit (Order 1): $y = ax + b$
   • Quadratic Fit (Order 2): $y = ax^2 + bx + c$ (convex or concave)
   • Higher-Order Fits: These correspond to cases where the curve exhibits mixed convex and concave behavior.

The behavior of $f(x)$ depends on the rate of change, captured by the sequence $\Delta_i = \frac{y_{i+1} - y_i}{x_{i+1} - x_i}$:

• Linear Fit: $\Delta_i$ is approximately constant.
• Quadratic Fit: $\Delta_i$ is either monotonically increasing (convex) or decreasing (concave).
• Higher-Order Fits: $\Delta_i$ does not follow a monotone pattern.

Experimental Insights

In our experiments, we did not observe non-monotonic behavior in $\{\Delta_i\}$, eliminating the need for higher-order fits. Instead, we compared linear (order 1) and quadratic (order 2) fits. Interestingly, the linear fit consistently provided better approximations. This is because, for most quadratic fits, the coefficient of the quadratic term was negligibly small, indicating a near-linear relationship.

To support these findings, we provide plots in Appendix B.3, illustrating the behavior of $f(x)$ under various fitting models. Furthermore, we conducted the following experiments to further validate the robustness of the linear fit. In the table below, you can see the average of the coefficients of quadratic terms when we use quadratic fit for the datasets, i.e. if we fit $y=a+bx+cx^2$ polynomial, we observe that quadratic term is mostly negligible, and the tends to be a linear fit.

W1.3 Relation with PH

If there is a relation with persistence homology, then it should be discussed.

Thank you for this question. In Section 3, we discussed the PH framework and emphasized the central role of filtration in this context. Following this foundation, in Section 4, we adopted the same approach as PH up to the filtration step, where a sequence of subgraphs $G_1 \subset G_2 \subset \dots \subset G_N$ is generated. However, our methodology diverges in the vectorization step, as we take a more direct approach to summarize the evolution pattern within the filtration sequence. In revision, we added a remark in Section 4 (before subsection 4.1) to clarify this connection.

We thank the reviewer for their valuable feedback, which, along with comments from others, has guided significant improvements to our paper. We hope our revisions and responses merit reconsideration of a higher evaluation.

W1. Motivation behind the method is lacking:

The paper provides very little motivation behind the actual methodology.

Thank you for raising this concern. Our motivation is twofold:

1. Simplifying persistent homology methods in graph representation learning.
2. Addressing the significant gap in graph dataset visualization and low-dimensional graph embeddings.

First goal - why is it important?: Persistent homology extracts features by recording the topological changes across filtration sequences of the data, and this approach has shown significant success in various settings. However, the approach is not feasible due to large computational costs.

First goal - how does TopER solve it?: We simplify and streamline the filtration process by using an evolutionary rate extracted through domain-agnostic, computationally cheap functions.

Second goal - why is it important?: While there has been considerable progress in node classification and visualization through node embeddings, there are virtually no methods, apart from Spectral Zoo, for graph classification visualization via graph embeddings.

Second goal - how does TopER solve it?: TopER embeddings summarize graph filtration and create visually distinct and interpretable 2D representations by leveraging simple regression on the filtration process. This approach allows for direct visualization of graph structures, enabling the identification of clusters, outliers, and comparative patterns across different datasets.

We have described these aspects in the introduction, but we agree that Section 4 could be an ideal place to elaborate on our contribution. We will change the section accordingly during our final revision.

W1.1 Method reasoning

It is not clear what the correlation between the number of edges and number of nodes of the induced graphs wrt a filtration function has to do with how the graph is characterized/classified.

Thank you for raising this point. We believe that topology is an excellent match for graph level tasks (as we outlined in page 2), as the field focuses on studying the properties of spaces and data that remain invariant under continuous deformations. Our motivation stems from the significant success of persistent homology (PH) in the past decade. In essence, PH tracks topological changes in a sequence of simplicial complexes induced by subgraphs $G_1 \subset G_2 \subset \dots \subset G_N$, which are generated based on a filtration function.

For example, consider the degree function as a filtration function. In this case, the lower-index subgraphs consist of nodes with low degrees—representing "less important" nodes in terms of degree—while higher-index subgraphs progressively activate nodes of greater importance according to the degree hierarchy. This filtration process provides a structured decomposition of the graph, where the filtration function organizes nodes and edges into a hierarchy of importance.

The sequence of subgraphs $\{G_i\}$ thus reveals how nodes and edges are distributed and connected with respect to this hierarchical structure. TopER (Topological Evolution Rate) captures this evolution pattern, quantifying how the graph's structure evolves as dictated by the filtration function. When the filtration function is relevant to the graph's domain—such as atomic weight in molecular graphs or transaction amounts in financial graphs—this evolution rate becomes both effective and interpretable.

Our visualizations demonstrate the utility of this approach, showing how this simple idea can effectively detect clusters and outliers in graph datasets. Additionally, by combining TopER features derived from multiple filtration functions, our model achieves performance comparable to state-of-the-art methods on benchmark graph classification datasets.

We believe this perspective clarifies the relationship between the evolution of node and edge distributions in the filtration process and the characterization of graphs in our method.