Unleashing Graph Transformers with Green and Martin Kernels

We sincerely appreciate your thoughtful review and valuable feedback on our manuscript. Your comments have helped us improve the clarity and completeness of our work. Below, we address your concerns point by point.

W1. "As discussed above, GRIT+GKSE and GRIT+MKSE outperform the baselines on 7 out of the 8 considered benchmark datasets. However, even though GKSE and MKSE are experimentally shown to perform better than their main competitor (RRWP encodings), it is not clear to me whether the improvements provided by the proposed encodings are statistically significant. On almost all benchmark datasets, the improvement over GRIT+RRWP appears to be minor."

Thank you for pointing this out. While we acknowledge that the performance improvements on some benchmarks may appear marginal, we would like to highlight that our proposed SEs demonstrate significant performance gains on datasets characterized by non-aperiodic and directed acyclic graph structures, specifically the PCQM4Mv2 and ckt-bench datasets. Additionally, as noted in the NeurIPS 2023 paper "Facilitating Graph Neural Networks with Random Walk on Simplicial Complexes", it is indeed challenging to achieve significant improvements by introducing a new positional or structural encoding alone. Therefore, while the gains may be marginal in some benchmarks, the substantial improvements on these specific datasets validate the effectiveness of our approach. We believe these results are meaningful and contribute to the ongoing research of structural encoding in this area.

W2. "Some details about the proposed models and the experimental setup are missing from the paper. The values of the different hyperparameters are provided in Tables 6 and 7 in the Appendix, but I could not find any details about the employed architecture. It is mentioned that the proposed encodings are integrated into GRIT, but for the paper to be self-contained, I would suggest the authors add a description of GRIT into the Appendix. More importantly, some details about how the proposed encodings are integrated into the models are also missing from the paper. GKSE and MKSE are defined (in l.216-l.222) over pairs of nodes. Hence, in my understanding, those encodings could not be used as initial node-level structural encodings. They could potentially be utilized as edge-level structural encodings. I would suggest the authors provide more details about the model."

We thank the reviewer for their thoughtful comments and for highlighting areas where additional clarity could improve the paper. Below, we address the specific points raised:

• Details About Model Architectures: While we understand the value of including detailed descriptions of the architectures used in our experiments, such as GRIT, we believe it would be inappropriate to describe extensively detailed architectures that we did not develop. For reference, we have provided a summary of all GNN models used in our experiments, along with citations, in Appendix A.2 (Baselines). We encourage readers to refer to the original papers for comprehensive descriptions of these architectures.

• Integration of GKSE and MKSE into GNN Models: We appreciate the reviewer’s observation regarding the lack of detailed explanations about how GKSE and MKSE are integrated into GNN models. Due to space limitations, we have included a brief explanation at the end of Section 4.1. Additionally, we have cited a relevant paper [1] that provides a clear formulation of absolute and relative SEs to further support readers in understanding how these encodings are incorporated.

We hope these additions address the reviewer’s concerns, and we thank you again for your valuable feedback, which has helped us improve the clarity and completeness of the paper.

[1] BLACK, Mitchell, et al. Comparing Graph Transformers via Positional Encodings. arXiv preprint arXiv:2402.14202, 2024.

W3. "I would encourage the authors to better motivate the use of the proposed encodings. Since RRWP encodings are also derived from the theory of random walks, why should one prefer the proposed encodings over RRWP encodings? Table 10 shows that computing GKSE and MKSE is computationally more expensive than computing RRWP encodings. Therefore, the authors should justify why one should choose the proposed encodings for a particular application."

Thank you for highlighting the need to better justify the use of our proposed encodings over RRWP. As discussed in Section 5.3 (Analysis of Experimental Results), our proposed GKSE and MKSE have special property to capture the structural properties of graphs that contain non-aperiodic substructures, such as molecular graphs and circuit graphs modeled as DAGs.

In our experiments, although the performance gains on the ZINC dataset may appear modest, we observed statistically significant improvements over RRWP on the PCQM4Mv2 dataset, which consists of approximately 3.7 million molecular graphs with majority part of non-aperiodic structures. These results demonstrate the advantages of our SEs in capturing complex structural information that RRWP might miss.

Regarding computational complexity:

• GKSE has the same theoretical complexity as RRWP, which is O(K∣V∣∣E∣), where K is the number of steps, ∣V∣ is the number of vertices, and ∣E∣ is the number of edges.
• MKSE requires slightly more computation, with a complexity of O(K∣V∣∣E∣+K∣E∣), due to additional normalization steps.

While MKSE is more computationally intensive than RRWP and GKSE, we believe this trade-off is justified in applications where capturing nuanced structural properties leads to better performance. Importantly, the computation of SEs is performed as a pre-processing step, so the additional computational cost does not impact the training or inference time of the model.

To provide practical insights, we measured the actual computation times on the PCQM4Mv2 dataset (~3.7 million graphs) using an NVIDIA A6000 GPU server:

• RRWP: 50 minutes 30 seconds
• GKSE: 51 minutes
• MKSE: 1 hour 26 minutes

As shown, the computation time for GKSE is nearly identical to RRWP, while MKSE takes longer due to extra calculations. Considering the minimal increase in computation time for GKSE and its consistent performance improvements across various datasets, we recommend using GKSE for applications involving molecular and circuit data. We have updated Section 5.3 in the manuscript to include this discussion and to better justify the choice of our proposed encodings for specific applications. We believe that our SEs offer meaningful advantages in representing complex graph structures, and we hope this clarification addresses your concerns.

W4. "Even though the paper is not hard to read, there exist some typos and other types of errors. For example, in l.126, "matrixwith" should be replaced with "matrix with". Also in l.290 (Theorem 3, part 2) "GKSE" should be replaced with "MKSE"."

Thank you for your meticulous reading of our manuscript and for pointing out these errors. We apologize for the oversight. We have corrected the typos you mentioned in the revised manuscript. Additionally, we have thoroughly proofread the entire document to identify and rectify any other mistakes or ambiguities. Your attention to detail has greatly contributed to improving the clarity and quality of our paper.

Q. "The proposed kernels appear to be very similar to the hitting times and commute time distances, two popular tools which are commonly used to analyze the structure of graphs. Is there a connection between the proposed kernels and hitting and commute times? If there is some connection, can you please provide more details?"

Classically, the Green kernel on graphs is defined as the Moore-Penrose inverse of the random walk normalized Laplacian. However, in the case of recurrent graphs, this traditional Green kernel differs from the random walk-based definition we introduce in the manuscript. Importantly, the Moore-Penrose Green kernel has well-established connections to hitting times and commute times. For example:

As shown in [2], the Green kernel can be computed using a formula involving hitting times and the stationary distribution.

Additionally, [3] demonstrates that deriving a kernel distance from the Green kernel results in the resistance distance, which is well-known to be proportional to commute time.

While these connections are significant, they differ from the finite-step Green kernel we propose. However, exploring potential relationships between our finite-step Green kernel and these classical tools could be a fascinating avenue for future research. We thank the reviewer for suggesting this direction and will consider it in future studies.

The Martin kernel presents a more complex, nonlinear structure, making it challenging to establish direct connections to hitting or commute times. While we were unable to identify such relationships, this could also be an intriguing area for further exploration.

Once again, thank you for your valuable feedback. Your comments have helped us enhance the clarity and relevance of our work.

[2] BEVERIDGE, Andrew. A hitting time formula for the discrete Green's function. Combinatorics, Probability and Computing, 2016, 25.3: 362-379.

[3] BLACK, Mitchell, et al. Comparing Graph Transformers via Positional Encodings. arXiv preprint arXiv:2402.14202, 2024.

1. We greatly appreciate your suggestion to test the performance of RRWP and GKSE on specific synthetic data to validate this claim.

To further investigate, we conducted experiments on subsets of the PCQM4Mv2 dataset, focusing on the presence of benzene rings (a representative non-aperiodic structure). Specifically, we sampled 50,000 graphs containing benzene rings (with-ring) and 50,000 graphs without any hexagonal ring structures (without-ring). These subsets allowed us to analyze the performance of RRWP and GKSE in isolation. Due to resource constraints and the similarity in performance between GKSE and MKSE, we only included GKSE in these comparisons.

For these experiments, we used the same hyperparameters as in the ZINC dataset experiments, with the exception of limiting the training to 100 epochs.

The results are summarized below:

From the results, we observe the following trends:

For with-ring graphs, GKSE consistently outperforms RRWP, demonstrating its ability to better capture the structural properties of non-aperiodic substructures. For without-ring graphs, RRWP shows better performance, likely due to its design being more suited to periodic or simpler graph structures.

We further analyzed the full PCQM4Mv2 dataset and found that the ratio of with-ring to without-ring graphs is approximately 1.95:1 (with 2,477,194 graphs containing rings and 1,269,426 without). This distribution explains why GKSE performs better than RRWP on the full dataset, as it better represents the dominant structural characteristics. 

Based on these findings, we hypothesize that using GKSE for with-ring graphs and RRWP for without-ring graphs could lead to further performance improvements on molecular datasets. This hybrid approach would leverage the strengths of each encoding based on the underlying graph structures.

2. Our newly developed structural encodings, GKSE and MKSE, aim to capture different aspects of graph structural information compared to existing positional encodings. This is evident in the analysis presented in Section 5.3, where we highlight the unique representational characteristics of our proposed methods.

Moreover, we emphasize that these encodings are not merely incremental improvements but involve the adaptation of abstract mathematical kernels, originally defined in theoretical stochastic processes, for practical application to real-world graph data. This required the development of sophisticated techniques to transform these kernels while preserving their mathematical significance. We believe this novel approach not only introduces a unique perspective to the field but also paves the way for exploring the use of other kernels on graphs beyond those introduced in this paper.

Your thoughtful comment has provided valuable insights that we plan to explore in future work. Once again, thank you for your detailed feedback, which has allowed us to conduct deeper analysis and propose new directions for improving our methods.

Q3. "Could it make sense to combine RRWP and/or these PEs?"

Thank you for this insightful question. As described in our paper, GKSE and MKSE are defined based on the expected number and probability of reaching one node from another during random walks, respectively.

To provide a more intuitive explanation:

• GKSE can be considered as the cumulative sum of RRWP values up to k steps, resulting in a k-dimensional vector that captures the aggregate influence over multiple steps.
• MKSE is essentially a normalized version of GKSE, focusing on the probability distribution over the paths.

Given that MKSE normalizes the cumulative information captured by GKSE, there is a degree of redundancy between the two encodings. To empirically assess whether combining them would enhance performance, we conducted experiments by concatenating various combinations of RRWP, GKSE, and MKSE on the ZINC and Ckt-bench-101 datasets.

The results showed that the concatenated encodings did not yield better performance compared to using each encoding individually. This suggests that the information overlap between GKSE and MKSE does not provide additive benefits when used together.

Based on these findings, we did not observe any performance gain from combining GKSE and MKSE.

We believe that selecting the appropriate structural encoding based on the dataset type is more beneficial than combining multiple encodings with overlapping information.

Once again, we thank you for your thoughtful comments and constructive suggestions. We believe that our responses and the revisions made have addressed your concerns adequately. Your feedback has been invaluable in enhancing the quality and rigor of our work.

We sincerely appreciate your thorough review and insightful feedback on our manuscript. Your comments have been instrumental in helping us refine and improve our work. Below, we address each of your concerns in detail.

W1. "The performance improvements seem minimal, if existent. Most of the numbers (if I didn't miss anything) are within standard deviation of the next best existing model, which is in several cases +RRWP."

Thank you for pointing this out. While we acknowledge that the performance improvements on some benchmarks may appear marginal, we would like to highlight that our proposed SEs demonstrate significant performance gains on datasets characterized by non-aperiodic and directed acyclic graph structures, specifically the PCQM4Mv2 and ckt-bench datasets. Additionally, as noted in the NeurIPS 2023 paper "Facilitating Graph Neural Networks with Random Walk on Simplicial Complexes", it is indeed challenging to achieve significant improvements by introducing a new positional or structural encoding alone. Therefore, while the gains may be marginal in some benchmarks, the substantial improvements on these specific datasets validate the effectiveness of our approach. We believe these results are meaningful and contribute to the ongoing research of structural encoding in this area. 

W2. "Given that this seems to be a general PE proposal a consideration of different graph transformers would be more suitable, i.e., beyond just GRIT."

Thank you for this valuable suggestion. We recognize the importance of demonstrating the general applicability of our proposed SEs across various graph transformer architectures. Due to time constraints, we focused our initial experiments on the GRIT architecture (SOTA). However, we agree that integrating our SEs into other models would provide a more comprehensive evaluation. To address your concern, we conducted additional experiments by integrating our SEs (GKSE and MKSE) into the GPS model, which has shown strong performance across various graph benchmarks. The results are summarized in the following table:

As shown in the table, the inclusion of GKSE and MKSE in the GPS model produced comparable results to the baseline GPS model across multiple datasets. In some cases, the performance slightly decreased. We observed similar trends when using RRWP as a SE with GPS, where the results were either comparable or marginally worse than the GPS baseline.

This suggests that the GPS architecture may not effectively leverage the information provided by random-walk-based SEs. In contrast, the GRIT architecture—for which RRWP was originally proposed—appears specifically designed to utilize this type of relative encoding, particularly within its attention mechanism. Consequently, the performance improvements observed with GKSE and MKSE are more pronounced in GRIT than in GPS. We think that further work is needed to explore graph transformer architectures that can maximize the utility of random-walk-based SEs. Our findings indicate that the current GPS model may not fully exploit this information, while GRIT is better suited for such encodings. Designing new architectures or modifying existing ones to better harness random-walk-based SEs represents a promising direction for future research.

W3. "A suitable baseline on the DAG data would be DAG transformer (Luo et al. Transformers over Directed Acyclic Graphs, NeurIPS'23)"

Thank you for bringing this to our attention. We have reviewed the DAG Transformer by Luo et al. (2023), which introduces the DAG reachability-based attention (DAGRA) and DAG Positional Encoding (DAGPE) to achieve SOTA performance on DAGs. Integrating DAGRA into the GRIT architecture presents significant challenges, primarily because their ablation studies indicate that full attention yields the best performance, and adapting DAGRA would require substantial modifications beyond the scope of our current work. Therefore, we maintained the original attention mechanism of GRIT for consistency. However, we have integrated DAGPE into GRIT and conducted experiments on the ckt-bench-101 and ckt-bench-301 datasets. The results are as follows:

These results have been added to the left side of Table 4 in the manuscript, and we have cited the DAG Transformer paper in the section of A.2. Including DAGPE as a baseline allows us to provide a more comprehensive comparison, demonstrating that our SEs offer competitive or superior performance on DAG data.

Q1. "Why is Table 3 missing the +RRWP baseline?"

We apologize for any confusion caused. The results labeled as GRIT in Table 3 actually represent GRIT+RRWP. This oversight occurred during the manuscript preparation, and we regret any misunderstanding it may have caused. We have thoroughly proofread the manuscript and updated Table 3 and the corresponding text to clearly indicate that these results are for GRIT with RRWP. Thank you for your meticulous reading and for bringing this error to our attention; it has allowed us to correct the manuscript and improve its clarity.

Q2. "The analysis in Fig. 1 is interesting, but the results shown in the tables do not show great differences. The text says "Consequently, RRWP, which is based on these transition probabilities, may fail to capture the structural properties of graphs containing non-aperiodic substructure". Could one maybe select corresponding data (sub)sets to show and test this?"

We greatly appreciate your suggestion to test the performance of RRWP and GKSE on specific subsets of data to validate this claim. Upon reflection, we agree that the original text may overstate the limitations of RRWP. To address this, we have revised the corresponding section of the manuscript to soften the claim and better align it with the empirical evidence.

To further investigate, we conducted experiments on subsets of the PCQM4Mv2 dataset, focusing on the presence of benzene rings (a representative non-aperiodic structure). Specifically, we sampled 50,000 graphs containing benzene rings (with-ring) and 50,000 graphs without any hexagonal ring structures (without-ring). These subsets allowed us to analyze the performance of RRWP and GKSE in isolation. Due to resource constraints and the similarity in performance between GKSE and MKSE, we only included GKSE in these comparisons.

For these experiments, we used the same hyperparameters as in the ZINC dataset experiments, with the exception of limiting the training to 100 epochs. The results are summarized below:

From the results, we observe the following trends:

For with-ring graphs, GKSE consistently outperforms RRWP, demonstrating its ability to better capture the structural properties of non-aperiodic substructures. For without-ring graphs, RRWP shows better performance, likely due to its design being more suited to periodic or simpler graph structures.

We further analyzed the full PCQM4Mv2 dataset and found that the ratio of with-ring to without-ring graphs is approximately 1.95:1 (with 2,477,194 graphs containing rings and 1,269,426 without). This distribution explains why GKSE performs better than RRWP on the full dataset, as it better represents the dominant structural characteristics. 

Based on these findings, we hypothesize that using GKSE for with-ring graphs and RRWP for without-ring graphs could lead to further performance improvements on molecular datasets. This hybrid approach would leverage the strengths of each encoding based on the underlying graph structures.

I've read through the rebuttals and I appreciate the authors detailed responses. Also Reviewer tZUc's detailed analysis is helpful. I am positive towards the paper, yet the results for GPS open up several questions, which I think go beyond this rebuttal. Of course, research should go beyond GPS, but to justify this research as a proposal beyond the single graph transformer GRIT, I think, some more analysis/evaluation is needed. So I agree with Reviewer 4iMa.

We sincerely appreciate your thoughtful review and valuable feedback on our manuscript. Your comments have helped us improve the clarity and completeness of our work. Below, we address your concerns point by point.

Q1. "Why are there inconsistencies in the chosen baselines across different benchmarks? E.g., why are GraphSAGE’s results not reported for all benchmarks?"

Thank you for pointing out the inconsistencies in our baseline selections across different benchmarks. The primary reason for this was the lack of access to the exact hyperparameters used in previous works for all models on every benchmark. To maintain consistency with reported results, we compiled performances from various prior studies, which sometimes led to missing entries for certain models like GraphSAGE. To address your concern, we have conducted additional experiments by running GraphSAGE on the two peptides benchmarks (func and struct) and the PCQM4Mv2 dataset.

The results are as follows:

We noticed that the performance of GraphSAGE on these benchmarks is lower than expected. This discrepancy is likely due to the difficulty in replicating the exact hyperparameter settings used in prior studies, as this information is often not publicly available. Despite this limitation, we believe that including these results provides a more comprehensive comparison and addresses the inconsistency you highlighted. However, please note that these results have not been added to the main text of the manuscript.

Q2 & W4. "Is there any trade-off between GKSE and MKSE? Is there any performance gain if we use both GKSE and MKSE? (e.g., their concatenation)"

Thank you for this insightful question. As described in our paper, GKSE and MKSE are defined based on the expected number and probability of reaching one node from another during random walks, respectively. To provide a more intuitive explanation:

• GKSE can be considered as the cumulative sum of RRWP values up to k steps, resulting in a k-dimensional vector that captures the aggregate influence over multiple steps.
• MKSE is essentially a normalized version of GKSE, focusing on the probability distribution over the paths. Given that MKSE normalizes the cumulative information captured by GKSE, there is a degree of redundancy between the two encodings. To empirically assess whether combining them would enhance performance, we conducted experiments by concatenating various combinations of RRWP, GKSE, and MKSE on the ZINC and Ckt-bench-101 datasets. The results showed that the concatenated encodings did not yield better performance compared to using each encoding individually. This suggests that the information overlap between GKSE and MKSE does not provide additive benefits when used together.

Based on these findings, we did not observe any performance gain from combining GKSE and MKSE. We believe that selecting the appropriate structural encoding based on the dataset type is more beneficial than combining multiple encodings with overlapping information.

W2. "Recently, for the sake of efficiency, several GTs have used more complex tokenization (e.g., NAGPhormer). Due to their scalability, they are more practical and also they have a better inductive bias about the graph structure. It would be interesting to see the effect of GKSE and MKSE on these models."

We deeply appreciate your mention of NAGPhormer, a milestone study that demonstrates exceptional performance on node classification tasks. As noted in our paper, we have cited and discussed NAGPhormer in the related work section due to its relevance and significance. However, the focus of our work is on graph classification/regression tasks, and the benchmarks used in our study differ from those in the NAGPhormer paper. This discrepancy makes a direct application of our SEs to NAGPhormer less straightforward. Nevertheless, we recognize the potential value of combining our random-walk-based SEs with NAGPhormer for large-graph tasks like node classification. Exploring how GKSE and MKSE can be adapted for such scenarios represents an exciting avenue for future research. We are grateful for your suggestion and plan to investigate this in subsequent studies.

Q3 & W3. "I believe the current experiments cannot support the effectiveness of GKSE and MKSE as they show the performance gain only on GRIT. Is this performance gain limited to only this model? How can using GKSE and MKSE as the structural encoding for other methods (GPS, NAGphormer, etc.) affect performance?"

Thank you for this valuable suggestion. We recognize the importance of demonstrating the general applicability of our proposed SEs across various graph transformer architectures. Due to time constraints, we focused our initial experiments on the GRIT architecture (SOTA). However, we agree that integrating our SEs into other models would provide a more comprehensive evaluation. To address your concern, we conducted additional experiments by integrating our SEs (GKSE and MKSE) into the GPS model, which has shown strong performance across various graph benchmarks. The results are summarized in the following table:

As shown in the table, the inclusion of GKSE and MKSE in the GPS model produced comparable results to the baseline GPS model across multiple datasets. In some cases, the performance slightly decreased. We observed similar trends when using RRWP as a SE with GPS, where the results were either comparable or marginally worse than the GPS baseline.

This suggests that the GPS architecture may not effectively leverage the information provided by random-walk-based SEs. In contrast, the GRIT architecture—for which RRWP was originally proposed—appears specifically designed to utilize this type of relative encoding, particularly within its attention mechanism. Consequently, the performance improvements observed with GKSE and MKSE are more pronounced in GRIT than in GPS. We think that further work is needed to explore graph transformer architectures that can maximize the utility of random-walk-based SEs. Our findings indicate that the current GPS model may not fully exploit this information, while GRIT is better suited for such encodings. Designing new architectures or modifying existing ones to better harness random-walk-based SEs represents a promising direction for future research.

W5. "(Minor) I suggest using a different citation format (e.g., using [13] instead of (13)). The current format results in confusion whether this is a citation or a reference to an equation (for example lines 222, 274, etc.)."

Thank you for bringing this to our attention. We agree that the citation format could lead to confusion between references and equation numbers. To enhance clarity, we have revised the manuscript to use "Eq. (x)" when referring to equations throughout the paper. We believe this change significantly improves the readability and overall quality of the manuscript.

Once again, we thank you for your insightful comments. We hope that our revisions and responses have adequately addressed your concerns. Your feedback has been invaluable in enhancing the quality of our work.

Q4 & W1. "My main concern is about the efficiency of the proposed methods: How can GKSE and MKSE affect the memory usage and training time of graph transformers (compared to common structural encodings and shortest path encodings)?"

We thank the reviewer for raising an important question regarding the efficiency of our proposed methods. Below, we provide a detailed response to address the concerns:

As summarized in Table 10, the memory usage and training time of the GRIT model with our proposed GKSE and MKSE are nearly identical to those of GRIT with the original RRWP. In fact, during actual training, structural encodings (SEs) are precomputed prior to the training epochs. Therefore, the choice of SEs has minimal impact on the memory usage and training time of the model itself. Any differences in computational cost are limited to the precomputation phase.

Nonetheless, the complexity of the precomputation process for the SEs cna be summarized as follows:

GKSE has the same theoretical complexity as RRWP, which is O(K∣V∣∣E∣), where K is the number of steps, ∣V∣ is the number of vertices, and ∣E∣ is the number of edges. MKSE requires slightly more computation, with a complexity of O(K∣V∣∣E∣+K∣E∣), due to additional normalization steps.

While MKSE is more computationally intensive than RRWP and GKSE, we believe this trade-off is justified in applications where capturing nuanced structural properties leads to better performance. 

To provide practical insights, we measured the actual computation times on the PCQM4Mv2 dataset (~3.7 million graphs) using an NVIDIA A6000 GPU server:

• RRWP: 50 minutes 30 seconds
• GKSE: 51 minutes
• MKSE: 1 hour 26 minutes

As shown, the computation time for GKSE is nearly identical to RRWP, while MKSE takes longer due to extra calculations. Considering the minimal increase in computation time for GKSE and its consistent performance improvements across various datasets, we recommend using GKSE for applications involving molecular and circuit data. We have updated Section 5.3 in the manuscript to include this discussion and to better justify the choice of our proposed encodings for specific applications. We believe that our SEs offer meaningful advantages in representing complex graph structures, and we hope this clarification addresses your concerns.

Further comparison with other SEs or Positional Encodings (PEs) is as follows:

In terms of time complexity, GKSE and MKSE are significantly more efficient than LapEig or SPD, except in extremely dense cases such as complete graphs. While the space complexity of GKSE and MKSE may appear to be K-times larger, this difference is negligible in practical training scenarios and is justified by the richer information they provide. Specifically, LapEig lacks relative information, and SPD represents SE values as a single scalar rather than a vector, limiting the expressiveness of these encodings.

We hope this explanation addresses the reviewer’s concerns and highlights the computational efficiency of our proposed methods. Thank you again for bringing up this important aspect of our work.

We appreciate the reviewer’s thoughtful feedback and alternative interpretations, which have helped us refine the clarity and scope of our arguments. Below, we address the specific concerns and provide clarifications.

We acknowledge that some of the statements in the original manuscript could potentially mislead readers. As a result, we have revised the relevant sections to provide a more accurate explanation of our findings and interpretations.

Our experimental results demonstrated that GKSEand MKSE outperform RRWP in both molecular and circuit graph datasets. We hypothesized that this improvement comes from the unique structural properties of these graphs, which we believe are better captured by GKSE and MKSE. As visualized in Figure 1 and Figure 2, GKSE and MKSE exhibit distinct patterns compared to RRWP, and these observations led us to hypothesize the reasons behind the performance enhancement. We have clarified in the revised manuscript that these insights are based on empirical observations rather than conclusive theoretical claims.

(Comments on 1 and 2) We appreciate the reviewer’s observation regarding non-aperiodic substructures and their potential impact on graph representations. To our knowledge, non-aperiodic substructures have not been explicitly studied in prior work. While there are studies on substructure counting [1], they primarily highlight how traditional GNNs fail to capture certain substructures. We have added this comment and citation at the end of Appendix D.1. We thank the reviewer for their valuable insight, which we plan to incorporate into future research to further explore this phenomenon in depth.

(Comment on 3) We agree that selecting an appropriate K based on graph diameter for individual graph samples could enhance the representation of DAGs. However, we note that in datasets where graph samples exhibit diverse diameters, smaller-diameter graphs may suffer from overly sparse representations when a fixed K is used. To address this, we have revised the manuscript to include a discussion of this trade-off and proposed to investigate whether such sparsity issues can be directly observed in future work.

The insights provided by the reviewer, particularly regarding the interpretation of non-aperiodic substructures and the potential advantages of sparsity in DAG representations, will guide our subsequent research. We believe that addressing these aspects can lead to a more comprehensive understanding of the effectiveness of GKSE and MKSE and their applications across diverse graph domains.

We thank the reviewer once again for their detailed feedback, which has allowed us to strengthen our discussion and identify new directions for future exploration.

[1] CHEN, Zhengdao, et al. Can graph neural networks count substructures?. Advances in neural information processing systems, 2020, 33: 10383-10395.

We sincerely appreciate your continued engagement and constructive feedback, which have further highlighted areas where our claims could be clarified and substantiated. Below, we address your comments in detail:

Clarification on Observations (Line 504): While we had previously softened the claims in the manuscript, we now recognize that our wording may still lead to potential misunderstandings. We have revised Line 504 to explicitly state that our observations do not serve as proof of the phenomena explaining the performance gains of GKSE and MKSE over RRWP. Instead, we have framed these as empirical observations that suggest possible explanations, pending further experimental verification.

Relation to [1]: We acknowledge that [1] does not directly support our claim regarding the efficacy of GKSE and MKSE. Instead, it was cited to emphasize that existing GNN models struggle to detect specific graph substructures. We understand how this could be misinterpreted as evidence for our findings, and we apologize for the confusion.

Sparse Representations in DAGs: Our claim that sparse representations in RRWP could weaken performance is an opinion based on our observations, but we acknowledge that we have not conducted targeted comparative experiments to directly support this assertion. However, we have revisited our results on the ckt-bench 101 dataset and specifically analyzed the MAE for test samples with smaller diameters. The results are as follows:

As we hypothesized, RRWP produces sparse representations for smaller-diameter graphs, which may result in a loss of critical structural information. In contrast, GKSE maintains denser representations, which appear to correlate with better performance in this scenario.

We are grateful for your insightful feedback, which has helped us refine our arguments and include additional analyses. We hope these clarifications and updates address your concerns. Thank you again for your valuable input.

I appreciate the authors’ effort in further revising the paper and presenting additional experimental results. I have some follow-up questions.

As we hypothesized, RRWP produces sparse representations for smaller-diameter graphs, which may result in a loss of critical structural information. In contrast, GKSE maintains denser representations, which appear to correlate with better performance in this scenario.

If I understand correctly, the table shows that GKSE performs better than RRWP on graphs with small diameters. At the same time, RRWP produces a sparse representation while GKSE does not. This experiment demonstrate the correlation between RRWP producing a sparser representation, and being outperformed by GKSE. Does this correlation imply causation? This is one of my original concerns with the line of reasoning of 479-509.

Additionally, are other factors considered and controlled? For example, graph diameter may have an influence of the perceptive field of RRWP. What other aspects of RRWP, GKSE, and MKSE, apart from sparsity, can be affected by diameter? Can these factors contribute to the change in performance?

Overall, the authors have made progress in making their argument more sound through revisions. Per conference regulation and time constraints, I do not request additional experimental evidence.